| 1 |
XML::Stream Tree Building 101 |
| 2 |
|
| 3 |
In order to not reinvent the wheel, XML::Stream uses the XML::Parser::Tree |
| 4 |
object as the data structure it passes around and stores. Two things need |
| 5 |
to be covered in order to understand what the data looks like when you get |
| 6 |
it from XML::Stream. |
| 7 |
|
| 8 |
|
| 9 |
|
| 10 |
Section 1: What does an XML::Parser::Tree object look like? |
| 11 |
|
| 12 |
The original documentation for XML::Parser::Tree can be a little hard to |
| 13 |
understand so we will go over the structure here for completeness. The |
| 14 |
that is built is essentially a big nested array. This guarantees that you |
| 15 |
see the tags in the order receded from the stream, and that the nesting of |
| 16 |
tags is maintained. The actual structure of the tree is complicated so |
| 17 |
let's cover an example: |
| 18 |
|
| 19 |
<A n='1>First<B n='2' m='bob'>Second</B>Third<C/></A> |
| 20 |
|
| 21 |
What we are working with is a nested <B/> tag inside the CDATA of <A/>. |
| 22 |
There are attributes on both tags that must be stored. To do this we use |
| 23 |
an array. The first element of the array is the root tag, or A. |
| 24 |
|
| 25 |
[ 'A' ] |
| 26 |
|
| 27 |
The second element is a list of all the things contained in <A/>. |
| 28 |
|
| 29 |
[ 'A', [ ] ] |
| 30 |
|
| 31 |
That new list is recursively built as you go down the hierarchy, so let's |
| 32 |
examine the structure. The first element of that new list is a hash of |
| 33 |
key/value pairs that represent the attributes of the tag you are looking |
| 34 |
at. In the case of the root tag <A/> the hash would be { 'n' => '1' }. So |
| 35 |
adding that to the list we get: |
| 36 |
|
| 37 |
[ 'A', [ { 'n' => '1' } ] ] |
| 38 |
|
| 39 |
Now, the rest of the new list is a set of two elements added at a time. |
| 40 |
Either a tag name followed by a list that represents the new tag, or a |
| 41 |
"0" (zero) followed by a string. This might be confusing so let's go to |
| 42 |
the example. As we parse the <A/> tag we see the string "First". So |
| 43 |
according to the rule we add a "0" and "First" to the list: |
| 44 |
|
| 45 |
[ 'A', [ { 'n' => '1' }, 0, "First" ] ] |
| 46 |
|
| 47 |
The next element is the <B/> tag. So the rules says that we add the |
| 48 |
tag and then a list that contains that tag: |
| 49 |
|
| 50 |
[ 'A', [ { 'n' => '1' }, 0, "First", 'B', [ ] ] ] |
| 51 |
|
| 52 |
Parsing the <B/> tag we see an attributes n = '2' and m = 'bob. So |
| 53 |
those go into a hash and that hash becomes the first element in the list |
| 54 |
for B: |
| 55 |
|
| 56 |
[ |
| 57 |
'A', [ { 'n' => '1' }, |
| 58 |
0, "First", |
| 59 |
'B', [ { 'n' => '2', 'm' => 'bob' } ] |
| 60 |
] |
| 61 |
] |
| 62 |
|
| 63 |
Next we see that <B/> contains the CDATA "Second" so that goes into |
| 64 |
the list for B: |
| 65 |
|
| 66 |
[ |
| 67 |
'A', [ { 'n' => '1' }, |
| 68 |
0, "First", |
| 69 |
'B', [ { 'n' => '2', 'm' => 'bob' } |
| 70 |
0, "Second" |
| 71 |
] |
| 72 |
] |
| 73 |
] |
| 74 |
|
| 75 |
<B/> closes and we leave this list and return to the list for <A/>. |
| 76 |
The next element there is CDATA so add a '0' and "Third" onto the list |
| 77 |
for A: |
| 78 |
|
| 79 |
[ |
| 80 |
'A', [ { 'n' => '1' }, |
| 81 |
0, "First", |
| 82 |
'B', [ { 'n' => '2', 'm' => 'bob' } |
| 83 |
0, "Second" |
| 84 |
] |
| 85 |
0, "Third" |
| 86 |
] |
| 87 |
] |
| 88 |
|
| 89 |
Now we see another tag, <C/>. So we add C and a list onto the A's list: |
| 90 |
|
| 91 |
[ |
| 92 |
'A', [ { 'n' => '1' }, |
| 93 |
0, "First", |
| 94 |
'B', [ { 'n' => '2', 'm' => 'bob' } |
| 95 |
0, "Second" |
| 96 |
] |
| 97 |
0, "Third", |
| 98 |
'C', [ ] |
| 99 |
] |
| 100 |
] |
| 101 |
|
| 102 |
Parsing <C/> we see that it has no attributes so we add an empty hash |
| 103 |
to the list for C: |
| 104 |
|
| 105 |
[ |
| 106 |
'A', [ { 'n' => '1' }, |
| 107 |
0, "First", |
| 108 |
'B', [ { 'n' => '2', 'm' => 'bob' } |
| 109 |
0, "Second" |
| 110 |
] |
| 111 |
0, "Third", |
| 112 |
'C', [ { } ] |
| 113 |
] |
| 114 |
] |
| 115 |
|
| 116 |
Next we see that <C/> contains no other data and ends in a />. This |
| 117 |
means that the tag is finished and contains no data. So close C and go |
| 118 |
back to <A/>. There is no other data in A so we close <A/> and we have |
| 119 |
our finished tree: |
| 120 |
|
| 121 |
[ |
| 122 |
'A', [ { 'n' => '1' }, |
| 123 |
0, "First", |
| 124 |
'B', [ { 'n' => '2', 'm' => 'bob' } |
| 125 |
0, "Second" |
| 126 |
] |
| 127 |
0, "Third", |
| 128 |
'C', [ { } ] |
| 129 |
] |
| 130 |
] |
| 131 |
|
| 132 |
|
| 133 |
|
| 134 |
Section II: How do we build the XML::Parser::Tree? |
| 135 |
|
| 136 |
For those who are interested in how we build a tree read on, for those |
| 137 |
that got enough out of the previous section, read anyway. |
| 138 |
|
| 139 |
Recursion would be too difficult to do in this linear problem so we |
| 140 |
looked at the problem and engineered a way to use a single list to build |
| 141 |
the structure. Every time a new tag is encountered a new list is added to |
| 142 |
end of the main list. When that list closes it is removed from the main |
| 143 |
list and then added onto the end of the previous element in the list, |
| 144 |
which is usually another list. In other words: |
| 145 |
|
| 146 |
The current list looks like this: |
| 147 |
|
| 148 |
[aaa] |
| 149 |
|
| 150 |
We see a new tag and make a new list: |
| 151 |
|
| 152 |
[aaa], [bbb] |
| 153 |
|
| 154 |
Populate that list and then close it. When we close we remove from the |
| 155 |
list and make it the last element in the previous list elements list. |
| 156 |
Confused? Watch: |
| 157 |
|
| 158 |
[aaa], [bbb] --> [aaa, [bbb] ] |
| 159 |
|
| 160 |
As we "recurse" the hierarchy and close tags we push the new list back |
| 161 |
up to the previous list element and create the proper nesting. |
| 162 |
|
| 163 |
Let's go over the same example from Section I. |
| 164 |
|
| 165 |
<A n='1>First<B n='2' m='bob'>Second</B>Third<C/></A> |
| 166 |
|
| 167 |
We start and push A on the list: |
| 168 |
|
| 169 |
[ 'A' ] |
| 170 |
|
| 171 |
Next we create a new list for the <A/> tag and populate the attribute |
| 172 |
hash: |
| 173 |
|
| 174 |
[ 'A', |
| 175 |
[ { 'n'=>'1' } ] |
| 176 |
] |
| 177 |
|
| 178 |
Now we see the CDATA: |
| 179 |
|
| 180 |
[ 'A', |
| 181 |
[ { 'n'=>'1' }, 0, "First" ] |
| 182 |
] |
| 183 |
|
| 184 |
Next it's the <B/> tag, so push B on the list and make a new list on |
| 185 |
the end of the main list: |
| 186 |
|
| 187 |
[ 'A', |
| 188 |
[ { 'n'=>'1' }, 0, "First", 'B' ], |
| 189 |
[ ] |
| 190 |
] |
| 191 |
|
| 192 |
Parsing the <B/> tag we see that is has attributes and CDATA: |
| 193 |
|
| 194 |
[ 'A', |
| 195 |
[ { 'n'=>'1' }, 0, "First", 'B' ], |
| 196 |
[ {'n'=>'2','m'=>"bob"}, 0, "Second" ] |
| 197 |
] |
| 198 |
|
| 199 |
Now <B/> closes and the magic begins... With the closing of <B/> we |
| 200 |
pop the last element off the list. Then we take that element and push it |
| 201 |
onto the last element of the main list. So we aren't pushing it onto the |
| 202 |
main list, but onto the last element of the main list: |
| 203 |
|
| 204 |
Popped value: [ {'n'=>'2','m'=>"bob"}, 0, "Second" ] |
| 205 |
|
| 206 |
List: [ 'A', |
| 207 |
[ { 'n'=>'1' }, 0, "First", 'B' ] |
| 208 |
] |
| 209 |
|
| 210 |
Push value on last element of list: |
| 211 |
[ 'A', |
| 212 |
[ { 'n'=>'1' }, 0, "First", 'B', [ {'n'=>'2','m'=>"bob"}, 0, "Second" ] ] |
| 213 |
] |
| 214 |
|
| 215 |
Now we see a CDATA and push that onto the last element in the list: |
| 216 |
|
| 217 |
[ 'A', |
| 218 |
[ { 'n'=>'1' }, |
| 219 |
0, "First", |
| 220 |
'B', [ {'n'=>'2','m'=>"bob"}, |
| 221 |
0, "Second" |
| 222 |
], |
| 223 |
0, "Third" |
| 224 |
] |
| 225 |
] |
| 226 |
|
| 227 |
Finally we see the <C/> tag, so a 'C' is pushed onto the list, and then |
| 228 |
a new list is created to contain the new tag: |
| 229 |
|
| 230 |
[ 'A', |
| 231 |
[ { 'n'=>'1' }, |
| 232 |
0, "First", |
| 233 |
'B', [ {'n'=>'2','m'=>"bob"}, |
| 234 |
0, "Second" |
| 235 |
], |
| 236 |
0, "Third", |
| 237 |
'C' |
| 238 |
], |
| 239 |
[ ] |
| 240 |
] |
| 241 |
|
| 242 |
<C/> no attributes so an empty hash is pushed onto the list: |
| 243 |
|
| 244 |
[ 'A', |
| 245 |
[ { 'n'=>'1' }, |
| 246 |
0, "First", |
| 247 |
'B', [ {'n'=>'2','m'=>"bob"}, |
| 248 |
0, "Second" |
| 249 |
], |
| 250 |
0, "Third", |
| 251 |
'C' |
| 252 |
], |
| 253 |
[ { } ] |
| 254 |
] |
| 255 |
|
| 256 |
<C/> contains no data so nothing is to be done there. The tag closes |
| 257 |
and we do the magic again. Pop the last element off the main list and |
| 258 |
push it onto the previous element's list: |
| 259 |
|
| 260 |
[ 'A', |
| 261 |
[ { 'n'=>'1' }, |
| 262 |
0, "First", |
| 263 |
'B', [ {'n'=>'2','m'=>"bob"}, |
| 264 |
0, "Second" |
| 265 |
], |
| 266 |
0, "Third", |
| 267 |
'C', [ { } ] |
| 268 |
] |
| 269 |
] |
| 270 |
|
| 271 |
Now <A/> closes so we pop the last element off the main list and push |
| 272 |
is onto a list with the previous element, which is the string 'A': |
| 273 |
|
| 274 |
[ 'A', |
| 275 |
[ { 'n'=>'1' }, |
| 276 |
0, "First", |
| 277 |
'B', [ {'n'=>'2','m'=>"bob"}, |
| 278 |
0, "Second" |
| 279 |
], |
| 280 |
0, "Third", |
| 281 |
'C', [ { } ] |
| 282 |
] |
| 283 |
] |
| 284 |
|
| 285 |
And voila! The tree is complete. We now call the callback function, |
| 286 |
pass it the tree, and then reset the tree for the next tag to be parsed. |
| 287 |
|