Design Note: Message Structure Traversal

Architecture and Design

Problem

The standard visitor design pattern traverses the entire structure. To “flatten” Loop definitions, we need to have a “definition” view which looks at details, and a “reference” view which doesn’t look at details.

Forces

Visitor and In-Order Traveral

Here’s the standard design pattern for Visitor:

class Visitor( object ):
    def preVisit( self, aNode ):
        pass # process aNode
    def postVisit( self, aNode ):
        pass # process aNode

class Structure( object ):
    def visit( self, aVisitor ):
        aVisitor.preVisit( self )
        for i in self.structure:
            i.visit( aVisitor )
        aVisitor.postVisit( self )

This implements basic in-order traversal of the structure

- preVisit( top )
    - preVisit( "I." )
        - preVisit( "I.A." )
        - postVisit( "I.A." )
        - preVisit( "I.B." )
        - postVisit( "I.B." )
    - postVisit( "I." )
    - preVisit( "II." )
        - preVisit( "II.A." )
        - postVisit( "II.A." )
        - preVisit( "II.B." )
        - postVisit( "II.B." )
    - postVisit( "II." )
- postVisit( top )

Depth-First Pre-Order Traversal

Some requirements are somewhat different from the standard traveral shown above. We need first to emit Definitions. Then we need to emit a resulting structure using References to the Definitions.

Note that each part (definitions and references) are completely flat. The definition of a Loop contains just Segments and references to any subLoops.

We want the following

- [preVisit( top )] no output
    - [preVisit( "I." )] no output
        - postVisit( "I.A." ) - definition
        - postVisit( "I.A." ) - definition
    - postVisit( "I." ) - definition with references to children
    - [preVisit( "II". )] no output
        - postVisit( "II.A." ) - definition
        - postVisit( "II.B." ) - definition
    - postVisit( "II." ) - definition with references to children
- postVisit( top ) - definition with references to children

In order to get this, we have to descend through each level of the structure until we reach the bottom-most level, where we begin emitting definitions.

The trick is that the “post” processing contains a review of the top-level of a structure with proper references inserted.

The ordinary visitor processing creates the definitions which are used by the “post” method.

Solution

The nature of the structures mean that we often have two kinds of traveral. For Segment-Composite-Element, we use ordinary in-order traversal, since this structure is essentially a Segment with the occasioanl sub-Segment (Composite).

For Message-Loop, we have to use a post-order traversal to be sure that loops emit their definition first (which will involve Segments) and then references to those definitions.

Consequence

We won’t have simple, single-visitor design.