.. _traversal:

########################################
Design Note: Message Structure Traversal
########################################

:ref:`architecture`

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.