1PPI::Tokenizer(3)     User Contributed Perl Documentation    PPI::Tokenizer(3)
2
3
4

NAME

6       PPI::Tokenizer - The Perl Document Tokenizer
7

SYNOPSIS

9         # Create a tokenizer for a file, array or string
10         $Tokenizer = PPI::Tokenizer->new( 'filename.pl' );
11         $Tokenizer = PPI::Tokenizer->new( \@lines       );
12         $Tokenizer = PPI::Tokenizer->new( \$source      );
13
14         # Return all the tokens for the document
15         my $tokens = $Tokenizer->all_tokens;
16
17         # Or we can use it as an iterator
18         while ( my $Token = $Tokenizer->get_token ) {
19               print "Found token '$Token'\n";
20         }
21
22         # If we REALLY need to manually nudge the cursor, you
23         # can do that to (The lexer needs this ability to do rollbacks)
24         $is_incremented = $Tokenizer->increment_cursor;
25         $is_decremented = $Tokenizer->decrement_cursor;
26

DESCRIPTION

28       PPI::Tokenizer is the class that provides Tokenizer objects for use in
29       breaking strings of Perl source code into Tokens.
30
31       By the time you are reading this, you probably need to know a little
32       about the difference between how perl parses Perl "code" and how PPI
33       parsers Perl "documents".
34
35       "perl" itself (the interpreter) uses a heavily modified lex
36       specification to specify its parsing logic, maintains several types of
37       state as it goes, and incrementally tokenizes, lexes AND EXECUTES at
38       the same time.
39
40       In fact, it is provably impossible to use perl's parsing method without
41       simultaneously executing code. A formal mathematical proof has been
42       published demonstrating the method.
43
44       This is where the truism "Only perl can parse Perl" comes from.
45
46       PPI uses a completely different approach by abandoning the (impossible)
47       ability to parse Perl the same way that the interpreter does, and
48       instead parsing the source as a document, using a document structure
49       independantly derived from the Perl documentation and approximating the
50       perl interpreter interpretation as closely as possible.
51
52       It was touch and go for a long time whether we could get it close
53       enough, but in the end it turned out that it could be done.
54
55       In this approach, the tokenizer "PPI::Tokenizer" is implemented
56       separately from the lexer PPI::Lexer.
57
58       The job of "PPI::Tokenizer" is to take pure source as a string and
59       break it up into a stream/set of tokens, and contains most of the
60       "black magic" used in PPI. By comparison, the lexer implements a
61       relatively straight forward tree structure, and has an implementation
62       that is uncomplicated (compared to the insanity in the tokenizer at
63       least).
64
65       The Tokenizer uses an immense amount of heuristics, guessing and cruft,
66       supported by a very VERY flexible internal API, but fortunately it was
67       possible to largely encapsulate the black magic, so there is not a lot
68       that gets exposed to people using the "PPI::Tokenizer" itself.
69

METHODS

71       Despite the incredible complexity, the Tokenizer itself only exposes a
72       relatively small number of methods, with most of the complexity
73       implemented in private methods.
74
75   new $file | \@lines | \$source
76       The main "new" constructor creates a new Tokenizer object. These
77       objects have no configuration parameters, and can only be used once, to
78       tokenize a single perl source file.
79
80       It takes as argument either a normal scalar containing source code, a
81       reference to a scalar containing source code, or a reference to an
82       ARRAY containing newline-terminated lines of source code.
83
84       Returns a new "PPI::Tokenizer" object on success, or throws a
85       PPI::Exception exception on error.
86
87   get_token
88       When using the PPI::Tokenizer object as an iterator, the "get_token"
89       method is the primary method that is used. It increments the cursor and
90       returns the next Token in the output array.
91
92       The actual parsing of the file is done only as-needed, and a line at a
93       time. When "get_token" hits the end of the token array, it will cause
94       the parser to pull in the next line and parse it, continuing as needed
95       until there are more tokens on the output array that get_token can then
96       return.
97
98       This means that a number of Tokenizer objects can be created, and won't
99       consume significant CPU until you actually begin to pull tokens from
100       it.
101
102       Return a PPI::Token object on success, 0 if the Tokenizer had reached
103       the end of the file, or "undef" on error.
104
105   all_tokens
106       When not being used as an iterator, the "all_tokens" method tells the
107       Tokenizer to parse the entire file and return all of the tokens in a
108       single ARRAY reference.
109
110       It should be noted that "all_tokens" does NOT interfere with the use of
111       the Tokenizer object as an iterator (does not modify the token cursor)
112       and use of the two different mechanisms can be mixed safely.
113
114       Returns a reference to an ARRAY of PPI::Token objects on success or
115       throws an exception on error.
116
117   increment_cursor
118       Although exposed as a public method, "increment_method" is implemented
119       for expert use only, when writing lexers or other components that work
120       directly on token streams.
121
122       It manually increments the token cursor forward through the file, in
123       effect "skipping" the next token.
124
125       Return true if the cursor is incremented, 0 if already at the end of
126       the file, or "undef" on error.
127
128   decrement_cursor
129       Although exposed as a public method, "decrement_method" is implemented
130       for expert use only, when writing lexers or other components that work
131       directly on token streams.
132
133       It manually decrements the token cursor backwards through the file, in
134       effect "rolling back" the token stream. And indeed that is what it is
135       primarily intended for, when the component that is consuming the token
136       stream needs to implement some sort of "roll back" feature in its use
137       of the token stream.
138
139       Return true if the cursor is decremented, 0 if already at the beginning
140       of the file, or "undef" on error.
141

NOTES

143   How the Tokenizer Works
144       Understanding the Tokenizer is not for the feint-hearted. It is by far
145       the most complex and twisty piece of perl I've ever written that is
146       actually still built properly and isn't a terrible spaghetti-like mess.
147       In fact, you probably want to skip this section.
148
149       But if you really want to understand, well then here goes.
150
151   Source Input and Clean Up
152       The Tokenizer starts by taking source in a variety of forms, sucking it
153       all in and merging into one big string, and doing our own internal line
154       split, using a "universal line separator" which allows the Tokenizer to
155       take source for any platform (and even supports a few known types of
156       broken newlines caused by mixed mac/pc/*nix editor screw ups).
157
158       The resulting array of lines is used to feed the tokenizer, and is also
159       accessed directly by the heredoc-logic to do the line-oriented part of
160       here-doc support.
161
162   Doing Things the Old Fashioned Way
163       Due to the complexity of perl, and after 2 previously aborted parser
164       attempts, in the end the tokenizer was fashioned around a line-buffered
165       character-by-character method.
166
167       That is, the Tokenizer pulls and holds a line at a time into a line
168       buffer, and then iterates a cursor along it. At each cursor position, a
169       method is called in whatever token class we are currently in, which
170       will examine the character at the current position, and handle it.
171
172       As the handler methods in the various token classes are called, they
173       build up a output token array for the source code.
174
175       Various parts of the Tokenizer use look-ahead, arbitrary-distance look-
176       behind (although currently the maximum is three significant tokens), or
177       both, and various other heuristic guesses.
178
179       I've been told it is officially termed a "backtracking parser with
180       infinite lookaheads".
181
182   State Variables
183       Aside from the current line and the character cursor, the Tokenizer
184       maintains a number of different state variables.
185
186       Current Class
187           The Tokenizer maintains the current token class at all times. Much
188           of the time is just going to be the "Whitespace" class, which is
189           what the base of a document is. As the tokenizer executes the
190           various character handlers, the class changes a lot as it moves a
191           long. In fact, in some instances, the character handler may not
192           handle the character directly itself, but rather change the
193           "current class" and then hand off to the character handler for the
194           new class.
195
196           Because of this, and some other things I'll deal with later, the
197           number of times the character handlers are called does not in fact
198           have a direct relationship to the number of actual characters in
199           the document.
200
201       Current Zone
202           Rather than create a class stack to allow for infinitely nested
203           layers of classes, the Tokenizer recognises just a single layer.
204
205           To put it a different way, in various parts of the file, the
206           Tokenizer will recognise different "base" or "substrate" classes.
207           When a Token such as a comment or a number is finalised by the
208           tokenizer, it "falls back" to the base state.
209
210           This allows proper tokenization of special areas such as __DATA__
211           and __END__ blocks, which also contain things like comments and
212           POD, without allowing the creation of any significant Tokens inside
213           these areas.
214
215           For the main part of a document we use PPI::Token::Whitespace for
216           this, with the idea being that code is "floating in a sea of
217           whitespace".
218
219       Current Token
220           The final main state variable is the "current token". This is the
221           Token that is currently being built by the Tokenizer. For certain
222           types, it can be manipulated and morphed and change class quite a
223           bit while being assembled, as the Tokenizer's understanding of the
224           token content changes.
225
226           When the Tokenizer is confident that it has seen the end of the
227           Token, it will be "finalized", which adds it to the output token
228           array and resets the current class to that of the zone that we are
229           currently in.
230
231           I should also note at this point that the "current token" variable
232           is optional. The Tokenizer is capable of knowing what class it is
233           currently set to, without actually having accumulated any
234           characters in the Token.
235
236   Making It Faster
237       As I'm sure you can imagine, calling several different methods for each
238       character and running regexes and other complex heuristics made the
239       first fully working version of the tokenizer extremely slow.
240
241       During testing, I created a metric to measure parsing speed called
242       LPGC, or "lines per gigacycle" . A gigacycle is simple a billion CPU
243       cycles on a typical single-core CPU, and so a Tokenizer running at
244       "1000 lines per gigacycle" should generate around 1200 lines of
245       tokenized code when running on a 1200 MHz processor.
246
247       The first working version of the tokenizer ran at only 350 LPGC, so to
248       tokenize a typical large module such as ExtUtils::MakeMaker took 10-15
249       seconds. This sluggishness made it unpractical for many uses.
250
251       So in the current parser, there are multiple layers of optimisation
252       very carefully built in to the basic. This has brought the tokenizer up
253       to a more reasonable 1000 LPGC, at the expense of making the code quite
254       a bit twistier.
255
256   Making It Faster - Whole Line Classification
257       The first step in the optimisation process was to add a hew handler to
258       enable several of the more basic classes (whitespace, comments) to be
259       able to be parsed a line at a time. At the start of each line, a
260       special optional handler (only supported by a few classes) is called to
261       check and see if the entire line can be parsed in one go.
262
263       This is used mainly to handle things like POD, comments, empty lines,
264       and a few other minor special cases.
265
266   Making It Faster - Inlining
267       The second stage of the optimisation involved inlining a small number
268       of critical methods that were repeated an extremely high number of
269       times. Profiling suggested that there were about 1,000,000 individual
270       method calls per gigacycle, and by cutting these by two thirds a
271       significant speed improvement was gained, in the order of about 50%.
272
273       You may notice that many methods in the "PPI::Tokenizer" code look very
274       nested and long hand. This is primarily due to this inlining.
275
276       At around this time, some statistics code that existed in the early
277       versions of the parser was also removed, as it was determined that it
278       was consuming around 15% of the CPU for the entire parser, while making
279       the core more complicated.
280
281       A judgment call was made that with the difficulties likely to be
282       encountered with future planned enhancements, and given the relatively
283       high cost involved, the statistics features would be removed from the
284       Tokenizer.
285
286   Making It Faster - Quote Engine
287       Once inlining had reached diminishing returns, it became obvious from
288       the profiling results that a huge amount of time was being spent
289       stepping a char at a time though long, simple and "syntactically
290       boring" code such as comments and strings.
291
292       The existing regex engine was expanded to also encompass quotes and
293       other quote-like things, and a special abstract base class was added
294       that provided a number of specialised parsing methods that would "scan
295       ahead", looking out ahead to find the end of a string, and updating the
296       cursor to leave it in a valid position for the next call.
297
298       This is also the point at which the number of character handler calls
299       began to greatly differ from the number of characters. But it has been
300       done in a way that allows the parser to retain the power of the
301       original version at the critical points, while skipping through the
302       "boring bits" as needed for additional speed.
303
304       The addition of this feature allowed the tokenizer to exceed 1000 LPGC
305       for the first time.
306
307   Making It Faster - The "Complete" Mechanism
308       As it became evident that great speed increases were available by using
309       this "skipping ahead" mechanism, a new handler method was added that
310       explicitly handles the parsing of an entire token, where the structure
311       of the token is relatively simple. Tokens such as symbols fit this
312       case, as once we are passed the initial sigil and word char, we know
313       that we can skip ahead and "complete" the rest of the token much more
314       easily.
315
316       A number of these have been added for most or possibly all of the
317       common cases, with most of these "complete" handlers implemented using
318       regular expressions.
319
320       In fact, so many have been added that at this point, you could arguably
321       reclassify the tokenizer as a "hybrid regex, char-by=char heuristic
322       tokenizer". More tokens are now consumed in "complete" methods in a
323       typical program than are handled by the normal char-by-char methods.
324
325       Many of the these complete-handlers were implemented during the writing
326       of the Lexer, and this has allowed the full parser to maintain around
327       1000 LPGC despite the increasing weight of the Lexer.
328
329   Making It Faster - Porting To C (In Progress)
330       While it would be extraordinarily difficult to port all of the
331       Tokenizer to C, work has started on a PPI::XS "accelerator" package
332       which acts as a separate and automatically-detected add-on to the main
333       PPI package.
334
335       PPI::XS implements faster versions of a variety of functions scattered
336       over the entire PPI codebase, from the Tokenizer Core, Quote Engine,
337       and various other places, and implements them identically in XS/C.
338
339       In particular, the skip-ahead methods from the Quote Engine would
340       appear to be extremely amenable to being done in C, and a number of
341       other functions could be cherry-picked one at a time and implemented in
342       C.
343
344       Each method is heavily tested to ensure that the functionality is
345       identical, and a versioning mechanism is included to ensure that if a
346       function gets out of sync, PPI::XS will degrade gracefully and just not
347       replace that single method.
348

TO DO

350       - Add an option to reset or seek the token stream...
351
352       - Implement more Tokenizer functions in PPI::XS
353

SUPPORT

355       See the support section in the main module.
356

AUTHOR

358       Adam Kennedy <adamk@cpan.org>
359
361       Copyright 2001 - 2009 Adam Kennedy.
362
363       This program is free software; you can redistribute it and/or modify it
364       under the same terms as Perl itself.
365
366       The full text of the license can be found in the LICENSE file included
367       with this module.
368
369
370
371perl v5.10.1                      2009-08-08                 PPI::Tokenizer(3)
Impressum