6 Feb 2003 raph   » (Master)

Enfilade theory

I had a truly great irc discussion with tor today. Among other things, he brought up Enfilade theory, which is one of the things the Xanadu folk came up with. It's easy to be put off by the presentation, including the strange terminology and all the boasting about how secret it all used to be, but I think at heart it's a useful tool for talking and reasoning about computations over trees.

As far as I can tell, the "wid" and "disp" properties are very similar to synthesized and inherited attributes in attribute grammars. The canonical example of "wid" is the number of bytes contained in the node and its descendants. Given two subtrees and their byte counts, it's easy to compute the byte count of their combination - just add them. Byte counting is simple, but there are lots more properties that can be computed in this manner. "Widiativeness" describes the generalization. One key insight is that all widiative properties are also associative.

Whatever properties are chosen, an enfilade is basically just a tree with the enfilade properties stored in the interior nodes. The tree engine has to update these values whenever the tree gets updated, but the cost is only proportional to the depth of the tree - O(log n) when the tree is balanced.

While "wid" properties propagate up, "disp" properties propagate down. In Fitz, the graphics state is essentially a disp property. You have interior nodes that set graphics state parameters, and affect all child nodes. When there are multiple nodes on a path from the root to a leaf node that set the same parameter, the deepest takes precedence. Similarly, clip paths intersect (which happens to be commutative), and coordinate transform matrices multiply.

Bounding boxes are a "wid" property, with the combining rule being rectangle union. In the PDF 1.4 data model, RGBA renderings of groups (whether nested as a Form XObject or q/Q pair) are almost wid, the exception being non-Normal blending modes. For these, the RGBA rendering of an object may depend on the colors that were rendered beneath it. This has implications for caching (I won't go into details here, because they're probably only interesting to one or two other people).

Another "wid" property is the tree representation for Athshe I've been thinking about for a while. You want to efficiently represent a tree with arbitrary structure, meaning it may or may not be balanced, and nodes may have ridiculously small or large fanout. The solution is to store a serialization of the tree in a B-tree, using open and close parentheses in addition to leaf symbols. There is not necessarily any relationship between the tree structure and the b-tree structure; the latter is always balanced with a tight distribution of fanouts. I wrote about storing some summary information about parenthesis balancing in B-tree nodes.

It makes sense to describe this summary info in enfilade terminology. My proposal is an enfilade that stores a "wid" property at each B-tree node. The "wid" property is a tuple of two integers. For open paren, it's (1, 0), for close paren it's (-1, -1), and for leaf nodes, it's (0, 0). The combining operator is defined as combine((a, b), (c, d)) = (a + c, min(b, a + d)). When this info is stored at each B-tree node, something magic happens: it's possible to do all the standard node navigation methods (parent, first child, prev and next sibling) using only O(log n) accesses to B-tree nodes (proof of this claim is left as an exercise to the reader).

I hope I've presented a wide range of issues for which enfilade theory is a useful reasoning tool. I think it's also useful to criticize bad designs. My favorite example is (of course) from the W3C.

The application of CSS stylesheets to XML trees is almost a disp property. However, the adjacent sibling selector in CSS2 breaks disp-ness. When I was working on implementing CSS, I looked through a lot of stylesheets, including searching all the XUL glorp in Mozilla at the time. I found a couple of uses of the adjacent sibling selector, but all could be factored out. In other words, the actual stylesheet had the disp property even though the adjacent sibling primitive lacked it. Again, this hurts performance and makes implementations far more complex than they should be. Perhaps if the designers of CSS2 had been aware of enfilade theory, they could have avoided this mistake.

(at dinner tonight, Heather asked me what I was thinking about. I responded, "enfilade theory". she asked me what that meant, and I promised her that after reading tonight's blog, she'd know more about it than she ever wanted to. hopefully, i've made good on my promise :)

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!