This file is indexed.

/usr/share/perl5/MKDoc/XML/TreeBuilder.pm is in libmkdoc-xml-perl 0.75-4.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
# -------------------------------------------------------------------------------------
# MKDoc::XML::TreeBuilder
# -------------------------------------------------------------------------------------
# Author : Jean-Michel Hiver.
# Copyright : (c) MKDoc Holdings Ltd, 2003
#
# This module turns an XML string into a tree of elements and returns the top elements.
# This assumes that the XML string is well-formed. Well. More or less :)
#
# This module is distributed under the same license as Perl itself.
# -------------------------------------------------------------------------------------
package MKDoc::XML::TreeBuilder;
use MKDoc::XML::Tokenizer;
use strict;
use warnings;


##
# $class->process_data ($xml);
# ----------------------------
# Parses $xml and turns it into a tree structure very similar
# to HTML::Element objects.
##
sub process_data
{
    my $class  = shift;
    my $tokens = MKDoc::XML::Tokenizer->process_data (@_);
    return _process_recurse ($tokens);
}


##
# $class->process_file ($filename);
# ---------------------------------
# Parses $xml and turns it into a tree structure very similar
# to HTML::Element objects.
##
sub process_file
{
    my $class  = shift;
    my $tokens = MKDoc::XML::Tokenizer->process_file (@_);
    return _process_recurse ($tokens);
}


##
# _process_recurse ($token_list);
# -------------------------------
# Turns $token_list array ref into a tree structure.
##
sub _process_recurse
{
    my $tokens = shift;
    my @result = ();
    
    while (@{$tokens})
    {
	# takes the first available token from the $tokens array reference
        my $token = shift @{$tokens};
	my $node  = undef;
	
	$node = $token->leaf();
	defined $node and do {
	    push @result, $node;
	    next;
	};
	
	$node = $token->tag_open();
	defined $node and do {
	    my $descendants   = _descendant_tokens ($token, $tokens);
	    $node->{_content} = _process_recurse ($descendants);
	    push @result, $node;
	    next;
	};

        my $token_as_string = $token->as_string();	
	die qq |parse_error: Is this XML well-formed? (unexpected closing tag "$token_as_string")|;
    }
    
    return wantarray ? @result : \@result;
}


##
# $class->descendant_tokens ($token, $tokens);
# --------------------------------------------
# Removes all tokens from $tokens which are descendants
# of $token - assuming that $token is an opening tag token.
#
# Returns all the tokens removed except for $token matching
# closing tag. So the closing tag is removed from $tokens
# but not returned.
##
sub _descendant_tokens
{
    my $token   = shift;
    my $tokens  = shift;
    my @res     = ();
    my $balance = 1;
    while (@{$tokens})
    {
	my $next_token = shift (@{$tokens});
	my $node       = undef;
	
	$node = $next_token->leaf();
	defined $node and do {
	    push @res, $next_token;
	    next;
	};
	
	$node = $next_token->tag_open();
	defined $node and do {
	    $balance++;
	    push @res, $next_token;
	    next;
	};
	
	$node = $next_token->tag_close();
	defined $node and do {
	    $balance--;
	    last if ($balance == 0);
	    push @res, $next_token;
	    next;
	};
	
	die "BUG: The program should never reach this statement.";
    }
    
    return \@res if ($balance == 0);
    my $token_as_string = $token->as_string();
    die qq |parse_error: Is this XML well-formed? (could not find closing tag for "$token_as_string")|;
}


1;


__END__


=head1 NAME

MKDoc::XML::TreeBuilder - Builds a parsed tree from XML data


=head1 SYNOPSIS

  my @top_nodes = MKDoc::XML::TreeBuilder->process_data ($some_xml);


=head1 SUMMARY

L<MKDoc::XML::TreeBuilder> uses L<MKDoc::XML::Tokenizer> to turn XML data
into a parsed tree. Basically it smells like an XML parser, looks like an
XML parser, and awfully overlaps with XML parsers.

But it's not an XML parser.

XML parsers are required to die if the XML data is not well formed.
MKDoc::XML::TreeBuilder doesn't give a rip: it'll parse whatever as long
as it's good enough for it to parse.

XML parsers expand entities. MKDoc::XML::TreeBuilder doesn't.
At least not yet.

XML parsers generally support namespaces. MKDoc::XML::TreeBuilder doesn't -
and probably won't.


=head1 DISCLAIMER

B<This module does low level XML manipulation. It will somehow parse even broken XML
and try to do something with it. Do not use it unless you know what you're doing.>


=head1 API

=head2 my @top_nodes = MKDoc::XML::Tokenizer->process_data ($some_xml);

Returns all the top nodes of the $some_xml parsed tree.

Although the XML spec says that there can be only one top element in an XML
file, you have to take two things into account:

1. Pseudo-elements such as XML declarations, processing instructions, and
comments.

2. MKDoc::XML::TreeBuilder is not an XML parser, it's not its job to care
about the XML specification, so having multiple top elements is just fine.


=head2 my $tokens = MKDoc::XML::Tokenizer->process_data ('/some/file.xml');

Same as MKDoc::XML::TreeBuilder->process_data ($some_xml), except that it
reads $some_xml from '/some/file.xml'.


=head1 Returned parsed tree - data structure

I have tried to make MKDoc::XML::TreeBuilder look enormously like HTML::TreeBuilder.
So most of this section is stolen and slightly adapted from the HTML::Element
man page.


START PLAGIARISM HERE

It may occur to you to wonder what exactly a "tree" is, and how
it's represented in memory.  Consider this HTML document:

  <html lang='en-US'>
    <head>
      <title>Stuff</title>
      <meta name='author' content='Jojo' />
    </head>
    <body>
     <h1>I like potatoes!</h1>
    </body>
  </html>

Building a syntax tree out of it makes a tree-structure in memory
that could be diagrammed as:

                     html (lang='en-US')
                      / \
                    /     \
                  /         \
                head        body
               /\               \
             /    \               \
           /        \               \
         title     meta              h1
          |       (name='author',     |
       "Stuff"    content='Jojo')    "I like potatoes"

This is the traditional way to diagram a tree, with the "root" at the
top, and it's this kind of diagram that people have in mind when they
say, for example, that "the meta element is under the head element
instead of under the body element".  (The same is also said with
"inside" instead of "under" -- the use of "inside" makes more sense
when you're looking at the HTML source.)

Another way to represent the above tree is with indenting:

  html (attributes: lang='en-US')
    head
      title
        "Stuff"
      meta (attributes: name='author' content='Jojo')
    body
      h1
        "I like potatoes"

Incidentally, diagramming with indenting works much better for very
large trees, and is easier for a program to generate.  The $tree->dump
method uses indentation just that way.

However you diagram the tree, it's stored the same in memory -- it's a
network of objects, each of which has attributes like so:

  element #1:  _tag: 'html'
               _parent: none
               _content: [element #2, element #5]
               lang: 'en-US'

  element #2:  _tag: 'head'
               _parent: element #1
               _content: [element #3, element #4]

  element #3:  _tag: 'title'
               _parent: element #2
               _content: [text segment "Stuff"]

  element #4   _tag: 'meta'
               _parent: element #2
               _content: none
               name: author
               content: Jojo

  element #5   _tag: 'body'
               _parent: element #1
               _content: [element #6]

  element #6   _tag: 'h1'
               _parent: element #5
               _content: [text segment "I like potatoes"]

The "treeness" of the tree-structure that these elements comprise is
not an aspect of any particular object, but is emergent from the
relatedness attributes (_parent and _content) of these element-objects
and from how you use them to get from element to element.

STOP PLAGIARISM HERE


This is pretty much the kind of data structure MKDoc::XML::TreeBuilder
returns. More information on different nodes and their type is available
in L<MKDoc::XML::Token>.


=head1 NOTES

Did I mention that MKDoc::XML::TreeBuilder is NOT an XML parser?


=head1 AUTHOR

Copyright 2003 - MKDoc Holdings Ltd.

Author: Jean-Michel Hiver

This module is free software and is distributed under the same license as Perl
itself. Use it at your own risk.


=head1 SEE ALSO

L<MKDoc::XML::Token>
L<MKDoc::XML::Tokenizer>

=cut