You are not logged in Log in Join
You are here: Home » Members » 4AM Productions (Evan Simpson) » Untangling Acquisition with Trees » howto_view

Log in



Untangling Acquisition with Trees


Created by 4am . Last modified 2004-01-07 14:30:04.

An alternate way to think about acquisition, by visualizing acquisition algebra expressions as binary trees.

The following is just an alternate way to think about acquisition, by visualizing acquisition algebra expressions as binary trees.

Every time you access an attribute of an object, under acquisition, you actually get a transparent acquisition wrapper. This wrapper has two slots, one for the newly acquired attribute, and one for the object through which it was acquired. The first is called aq_self, and the second is aq_parent. A sequence of attribute accesses, such as ZPublisher traversal of a URL, creates a binary tree of objects and wrappers.

Suppose, for example, that we have a Zope root object Z, which directly contains objects A and C. A contains B. In traversing the URL /A/B/C, the series of trees below is created. The trees are laid out so that the left child of each node is its aq_self, and the right child is its aq_parent. The aq_base and aq_inner node of each tree is also labelled, and the AA expression for each tree appears underneath it.

1.               Z

2.               Z.A
       aq_inner / \
               /   \
              /     \
             A       Z
 aq_self,aq_base   aq_parent
              (A o Z)

3.                 Z.A.B
         aq_inner / \
                 /   \
                B     o aq_parent
    aq_self,aq_base  / \
                    /   \             
                   A     Z
              (B o (A o Z))

4.                   Z.A.B.C
                    / \
                   /   \
                  /     \
                 /       \
                /         \
       aq_self o           o aq_parent
              / \         / \
             /   \       B   \
            /     \           \
  aq_inner o       o           o
          / \     / \         / \
 aq_base C   Z   A   Z       A   Z
   (((C o Z) o (A o Z)) o (B o (A o Z)))

The aq_base of each tree is the leftmost leaf. This is the most recently acquired object without any wrappers. The node above it is aq_inner, the "smallest" wrapper containing the acquired object.

The point of all this wrapping and tree building is to make available the properties and contents of each object that was visited in order to reach the "target" object. If you ask "Z.A.B.C" for the value of "foo", the acquisition machinery will search the acquisition tree depth-first, left-to-right. If "C" has "foo" as an attribute, the search will stop right there. Otherwise, it will proceed to "Z", then "A", then (thanks to internal optimizations which avoid redundancy) "B". You can think of the tree as defining an "acquisition order" in which the objects will be searched.

You can think of transforming between the tree and algebraic forms by "lifting" the algebraic expression at the "o"s, or "flattening" the tree and putting parentheses around each subtree.

The algebraic form allows you to read off the acquisition order from left to right, ignoring duplicates. Thus, in step 3 the order is [B, A, Z], while in step 4 it is [C, Z, A, B]. Notice that by acquiring C, we turn the acquisition order inside out. The first rule, here, is that the acquisition order always begins with the direct containment path to the root. After that, it visits other objects in an order which can be roughly characterized as their "distance" from the base object. It is not a good idea to create applications which depend on this latter part of the acquisition order, as it can be highly nonintuitive.

If the transition from step 3 to step 4 boggles you, try thinking about it like this: the aq_parent of each tree (its right subtree) is the entire tree from the previous step, since that is the context from which we are acquiring. If C were an attribute of B (the aq_base of the old tree) then it would be the new aq_self (left child). It isn't, though, so we have to acquire it from Z.A, the tree from step 2. This makes the new aq_self a wrapper that has the tree from step 2 as its aq_parent. C is not an attribute of A, so we have to acquire it from Z. This gives us an aq_self that is a wrapper that has Z as its aq_parent. Z has C as an attribute, so it is filled in as the final aq_self.