Debian Codegraph @

INFO

raw
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