XML::Stream Tree Building 101

  In order to not reinvent the wheel, XML::Stream uses the XML::Parser::Tree
object as the data structure it passes around and stores.  Two things need
to be covered in order to understand what the data looks like when you get
it from XML::Stream.



Section 1:  What does an XML::Parser::Tree object look like?

  The original documentation for XML::Parser::Tree can be a little hard to
understand so we will go over the structure here for completeness.  The
that is built is essentially a big nested array.  This guarantees that you
see the tags in the order receded from the stream, and that the nesting of
tags is maintained.  The actual structure of the tree is complicated so
let's cover an example:

  <A n='1>First<B n='2' m='bob'>Second</B>Third<C/></A>

  What we are working with is a nested <B/> tag inside the CDATA of <A/>.
There are attributes on both tags that must be stored.  To do this we use
an array.  The first element of the array is the root tag, or A.

  [ 'A' ]

  The second element is a list of all the things contained in <A/>.

  [ 'A', [ ] ]

  That new list is recursively built as you go down the hierarchy, so let's
examine the structure.  The first element of that new list is a hash of
key/value pairs that represent the attributes of the tag you are looking
at.  In the case of the root tag <A/> the hash would be { 'n' => '1' }.  So
adding that to the list we get:

  [ 'A', [ { 'n' => '1' } ] ]

  Now, the rest of the new list is a set of two elements added at a time.
Either a tag name followed by a list that represents the new tag, or a
"0" (zero) followed by a string.  This might be confusing so let's go to
the example.  As we parse the <A/> tag we see the string "First".  So
according to the rule we add a "0" and "First" to the list:

  [ 'A', [ { 'n' => '1' }, 0, "First" ] ]

  The next element is the <B/> tag.  So the rules says that we add the
tag and then a list that contains that tag:

  [ 'A', [ { 'n' => '1' }, 0, "First", 'B', [ ] ] ]

  Parsing the <B/> tag we see an attributes n = '2' and m = 'bob.  So
those go into a hash and that hash becomes the first element in the list
for B:

  [
    'A', [ { 'n' => '1' },
           0, "First",
           'B', [ { 'n' => '2', 'm' => 'bob' } ]
         ]
  ]

  Next we see that <B/> contains the CDATA "Second" so that goes into
the list for B:

  [
    'A', [ { 'n' => '1' },
           0, "First",
           'B', [ { 'n' => '2', 'm' => 'bob' }
                  0, "Second"
                ]
         ]
  ]

  <B/> closes and we leave this list and return to the list for <A/>.
The next element there is CDATA so add a '0' and "Third" onto the list
for A:

  [
    'A', [ { 'n' => '1' },
           0, "First",
           'B', [ { 'n' => '2', 'm' => 'bob' }
                  0, "Second"
                ]
           0, "Third"
         ]
  ]

  Now we see another tag, <C/>.  So we add C and a list onto the A's list:

  [
    'A', [ { 'n' => '1' },
           0, "First",
           'B', [ { 'n' => '2', 'm' => 'bob' }
                  0, "Second"
                ]
           0, "Third",
           'C', [ ]
         ]
  ]

  Parsing <C/> we see that it has no attributes so we add an empty hash
to the list for C:

  [
    'A', [ { 'n' => '1' },
           0, "First",
           'B', [ { 'n' => '2', 'm' => 'bob' }
                  0, "Second"
                ]
           0, "Third",
           'C', [ { } ]
         ]
  ]

  Next we see that <C/> contains no other data and ends in a />.  This
means that the tag is finished and contains no data.  So close C and go
back to <A/>.  There is no other data in A so we close <A/> and we have
our finished tree:

  [
    'A', [ { 'n' => '1' },
           0, "First",
           'B', [ { 'n' => '2', 'm' => 'bob' }
                  0, "Second"
                ]
           0, "Third",
           'C', [ { } ]
         ]
  ]



Section II:  How do we build the XML::Parser::Tree?

  For those who are interested in how we build a tree read on, for those
that got enough out of the previous section, read anyway.

  Recursion would be too difficult to do in this linear problem so we
looked at the problem and engineered a way to use a single list to build
the structure.  Every time a new tag is encountered a new list is added to
end of the main list.  When that list closes it is removed from the main
list and then added onto the end of the previous element in the list,
which is usually another list.  In other words:

  The current list looks like this:

  [aaa]

  We see a new tag and make a new list:

  [aaa], [bbb]

  Populate that list and then close it.  When we close we remove from the
list and make it the last element in the previous list elements list.
Confused?  Watch:

  [aaa], [bbb] -->  [aaa, [bbb] ]

  As we "recurse" the hierarchy and close tags we push the new list back
up to the previous list element and create the proper nesting.

  Let's go over the same example from Section I.

  <A n='1>First<B n='2' m='bob'>Second</B>Third<C/></A>

  We start and push A on the list:

  [ 'A' ]

  Next we create a new list for the <A/> tag and populate the attribute
hash:

  [ 'A',
    [ { 'n'=>'1' } ]
  ]

  Now we see the CDATA:

  [ 'A',
    [ { 'n'=>'1' }, 0, "First" ]
  ]

  Next it's the <B/> tag, so push B on the list and make a new list on
the end of the main list:

  [ 'A',
    [ { 'n'=>'1' }, 0, "First", 'B' ],
    [ ]
  ]

  Parsing the <B/> tag we see that is has attributes and CDATA:

  [ 'A',
    [ { 'n'=>'1' }, 0, "First", 'B' ],
    [ {'n'=>'2','m'=>"bob"}, 0, "Second" ]
  ]

  Now <B/> closes and the magic begins...  With the closing of <B/> we
pop the last element off the list.  Then we take that element and push it
onto the last element of the main list.  So we aren't pushing it onto the
main list, but onto the last element of the main list:

  Popped value: [ {'n'=>'2','m'=>"bob"}, 0, "Second" ]

  List:         [ 'A',
                  [ { 'n'=>'1' }, 0, "First", 'B' ]
                ]

  Push value on last element of list:
  [ 'A',
    [ { 'n'=>'1' }, 0, "First", 'B', [ {'n'=>'2','m'=>"bob"}, 0, "Second" ] ]
  ]

  Now we see a CDATA and push that onto the last element in the list:

  [ 'A',
    [ { 'n'=>'1' },
      0, "First",
      'B', [ {'n'=>'2','m'=>"bob"},
             0, "Second"
           ],
      0, "Third"
    ]
  ]

  Finally we see the <C/> tag, so a 'C' is pushed onto the list, and then
a new list is created to contain the new tag:

  [ 'A',
    [ { 'n'=>'1' },
      0, "First",
      'B', [ {'n'=>'2','m'=>"bob"},
             0, "Second"
           ],
      0, "Third",
      'C'
    ],
    [ ]
  ]

  <C/> no attributes so an empty hash is pushed onto the list:

  [ 'A',
    [ { 'n'=>'1' },
      0, "First",
      'B', [ {'n'=>'2','m'=>"bob"},
             0, "Second"
           ],
      0, "Third",
      'C'
    ],
    [ { } ]
  ]

  <C/> contains no data so nothing is to be done there.  The tag closes
and we do the magic again.  Pop the last element off the main list and
push it onto the previous element's list:

  [ 'A',
    [ { 'n'=>'1' },
      0, "First",
      'B', [ {'n'=>'2','m'=>"bob"},
             0, "Second"
           ],
      0, "Third",
      'C', [ { } ]
    ]
  ]

  Now <A/> closes so we pop the last element off the main list and push
is onto a list with the previous element, which is the string 'A':

  [ 'A',
    [ { 'n'=>'1' },
      0, "First",
      'B', [ {'n'=>'2','m'=>"bob"},
             0, "Second"
           ],
      0, "Third",
      'C', [ { } ]
    ]
  ]

  And voila!  The tree is complete.  We now call the callback function,
pass it the tree, and then reset the tree for the next tag to be parsed.