RE_ast.pm untested

filter: Statementstmt 0.0% 0 / 464 Branchbran 0.0% 0 / 116 Conditioncond 0.0% 0 / 30 MC/DCmcdc 0.0% 0 / 18 Subroutinesub 0.0% 0 / 61 Podpod 0.0% 0 / 56 totaltotal 0.0% 0 / 745 CC 59 SCAR 31.8
CC
59
Cov
0%
nfa
72.0
nfa
72.0
qm
56.0
CRAP 23.9
1 # RE_ast.pmc
2 #
3 # Copyright 2009-2010, Larry Wall
4 #
5 # You may copy this software under the terms of the Artistic License,
6 # version 2.0 or later.
7  
8 package main;
9 use utf8;
10 use strict; use warnings;
11 use DEBUG;
12 use Encode;
13  
14 # The DFA engine has two priorities; top priority is to generate the correct
15 # pattern prefixes; second is to generate as much fate as it can.
16  
17 # [conjectural]
18 # We use two data structures to represent NFAs. The NFA description tree
19 # (NFA::* but not NFA::Node, NFA::Lazy) is statically built; it is a near 1:1
20 # mapping of the RE_ast structure. The NFA description tree is used to
21 # generate the NFA construction tree, which is lazily built.
22 {
23 package NFA::Lazy;
24 sub new { bless [ @_ ], 'NFA::Lazy' }
25 sub reify {
26 my $self = shift;
27 my ($node, $prefix, $continue) = splice @$self;
28 bless $self, 'NFA::Node';
29 $node->construct($self, $prefix, $continue);
30 }
31 }
32  
33 {
34 package NFA::Node;
35 sub reify { }
36 }
37  
38 {
39 package NFA::seq;
40 sub new {
41 my ($left, $right) = @_;
42 my $literal = $left->{literal};
43 my $litlen = $left->{litlen};
44 if ($literal) {
45 $literal &&= $right->{literal};
46 $litlen += ($right->{litlen} // 0);
47 }
48 bless { left => $left, right => $right, literal => $literal,
49 litlen => $litlen, fates => ($left->{fates} || $right->{fates}) },
50 'NFA::seq';
51 }
52  
53 sub construct {
54 my ($self, $node, $pre_fates, $continue) = @_;
55  
56 $self->{left}->construct($node, $pre_fates, sub {
57 my $mid_fates = shift;
58 NFA::Lazy->new($self->{right}, $mid_fates, $continue);
59 });
60 }
61 }
62  
63 #############################################################
64 # longest token set generator
65 #############################################################
66  
67 # $::DEBUG |= -1;
68 sub qm { my $s = shift;
69 $s = $s->[0] if ref $s eq 'ARRAY'; # only count first token of circumfix or postcircumfix
70 my $r = '';
71 for (split(//,$s)) {
72 if ($_ eq " ") { $r .= '\x20' }
73 elsif ($_ eq "\t") { $r .= '\t' }
74 elsif ($_ eq "\n") { $r .= '\n' }
75 elsif ($_ =~ m/^\w$/) { $r .= $_ }
76 elsif ($_ eq '<' | $_ eq '>') { $r .= $_ }
77 else { $r .= '\\' . $_ }
78 }
79 $r;
80 }
81  
82 sub here {
83 return unless $::DEBUG & DEBUG::longest_token_pattern_generation;
84 my $arg = shift;
85 my $lvl = 0;
86 while (caller($lvl)) { $lvl++ }
87 my ($package, $file, $line, $subname, $hasargs) = caller(0);
88  
89 my $name = $package; # . '::' . substr($subname,1);
90 if (defined $arg) {
91 $name .= " " . $arg;
92 }
93 ::deb("\t", ':' x $lvl, ' ', $name, " [", $file, ":", $line, "]") if $::DEBUG & DEBUG::longest_token_pattern_generation;
94 }
95  
96 { package nfa;
97  
98 # Rules: Don't call $cont more than once with the same fate. Don't instantiate
99 # a node more than once with the same fate.
100 sub node {
101 my $id = @::NFANODES;
102 #::deb("creating direct node $id") if $::DEBUG & DEBUG::longest_token_pattern_generation;
103 push @::NFANODES, [ $id, @_ ];
104 $id;
105 }
106  
107 sub gnode {
108 my $id = @::NFANODES;
109 #::deb("creating node $id via " . ref($_[0])) if $::DEBUG & DEBUG::longest_token_pattern_generation;
110 push @::NFANODES, [ $id ];
111 $_[0]->construct($::NFANODES[$id], $_[1], $_[2]);
112 $id;
113 }
114  
115 sub rgnode { my ($ob, $n, $f, $c) = @_;
116 #::deb("forwarding node " . $n->[0] . " to " . ref($ob)) if $::DEBUG & DEBUG::longest_token_pattern_generation;
117 $ob->construct($n, $f, $c);
118 }
119  
120 sub nfa::null::construct { my ($self, $node, $fate, $cont) = @_;
121 push @$node, $cont ? (undef, undef, $cont->($fate)) : ($fate);
122 }
123  
124 sub nfa::imp::construct { my ($self, $node, $fate, $cont) = @_;
125 push @$node, $fate;
126 }
127  
128 our $NULL = bless({ m => [], nr => 0, l => 1, ll => 0 }, 'nfa::null');
129 our $IMP = bless({ m => [], nr => 1, l => 0, ll => 0 }, 'nfa::imp');
130  
131 # When a non-LTM alternation or quantifier is applied to a subregex, it becomes
132 # impossible to control where subsequent tokens match, so we can't copy fates.
133 sub nfa::horizon::construct { my ($self, $node, $fate, $cont) = @_;
134 my @fate = @$fate;
135 $fate[0] = 1;
136 nfa::rgnode($self->{i}, $node, \@fate, $cont);
137 }
138 sub horizon { my ($inner) = @_;
139 bless({ m => $inner->{m}, nr => $inner->{nr}, l => $inner->{l},
140 ll => $inner->{ll}, i => $inner }, 'nfa::horizon');
141 }
142  
143 sub method { my ($mp, $inner) = @_;
144 bless({ %$inner, m => [ @{ $inner->{m} }, $mp ] }, ref($inner));
145 }
146  
147 sub noreturn { $_[0]{nr} }
148  
149 sub nfa::seq::construct { my ($self, $node, $fate, $cont) = @_;
150 nfa::rgnode($self->{fst}, $node, $fate, sub {
151 nfa::gnode($self->{snd}, $_[0], $cont) });
152 }
153 sub seq { my ($fst, $snd) = @_;
154 bless({ m => [ @{ $fst->{m} }, @{ $snd->{m} } ],
155 nr => $fst->{nr} || $snd->{nr}, l => $fst->{l} && $snd->{l},
156 ll => ($fst->{l} ? $fst->{ll} + $snd->{ll} : $fst->{ll}),
157 fst => $fst, snd => $snd }, 'nfa::seq');
158 }
159  
160 sub nfa::star::construct { my ($self, $node, $fate, $cont) = @_;
161 my @fate = @$fate;
162 $fate[0] = 1;
163 push @$node, ($cont ? (undef, undef, $cont->(\@fate)) : (\@fate)),
164 undef, nfa::gnode($self->{i}, \@fate, sub { $node->[0] });
165 }
166 sub star { my ($in) = @_;
167 bless({ m => $in->{m}, nr => 0, l => 0, ll => 0, i => $in },
168 'nfa::star');
169 }
170  
171 sub nfa::opt::construct { my ($self, $node, $fate, $cont) = @_;
172 my @fate = @$fate;
173 $fate[0] = 1;
174 my $end = $cont ? $cont->(\@fate) : nfa::node(\@fate);
175 push @$node, undef, undef, $end,
176 undef, nfa::gnode($self->{i}, \@fate, sub { $end });
177 }
178 sub opt { my ($in) = @_;
179 bless({ m => $in->{m}, nr => 0, l => 0, ll => 0, i => $in },
180 'nfa::opt');
181 }
182  
183 sub nfa::ltm::construct { my ($self, $node, $fate, $cont) = @_;
184 push @$node, undef;
185 if ($fate->[0]) {
186 my $end;
187 for my $br (@{ $self->{br} }) {
188 push @$node, undef, nfa::gnode($br->[1], $fate,
189 sub { $end //= $cont->($fate) });
190 }
191 } else {
192 my $ix;
193 for my $br (@{ $self->{br} }) {
194 my @fate = @$fate;
195 push @fate, $self->{t}, $br->[0], pack("NN",
196 ~($br->[1]{ll}), $ix++);
197 push @$node, undef, nfa::gnode($br->[1], \@fate, $cont);
198 }
199 }
200 }
201 sub ltm { my ($tag, @branches) = @_;
202 my $nr = 1;
203 my @m;
204 for (@branches) {
205 $nr &&= $_->[1]{nr};
206 push @m, @{ $_->[1]{m} };
207 }
208 bless({ m => \@m, nr => $nr, l => 0, ll => 0, t => $tag, br => \@branches },
209 'nfa::ltm');
210 }
211  
212 sub nfa::cclass::construct { my ($self, $node, $fate, $cont) = @_;
213 my $end = $cont ? $cont->($fate) : nfa::node($fate);
214 push @$node, undef, map { $_, $end } @{ $self->{t} };
215 }
216 sub cclass { my @terms = @_;
217 bless({ m => [], nr => 0, l => 0, ll => 0, t => \@terms }, 'nfa::cclass');
218 }
219  
220 sub nfa::string::construct { my ($self, $node, $fate, $cont) = @_;
221 my ($i, $t) = @{ $self }{ 'i', 't' };
222 if ($t eq '') {
223 nfa::rgnode($NULL, $node, $fate, $cont);
224 } else {
225 my @nexts = ((map { nfa::node() } (1 .. length($t) - 1)),
226 ($cont ? $cont->($fate) : nfa::node($fate)));
227 for my $ch (split //, $t) {
228 push @$node, undef, map { [$_], $nexts[0] }
229 ($i ? (uc($ch), lc($ch)) : $ch);
230 $node = $::NFANODES[$nexts[0]];
231 shift @nexts;
232 }
233 }
234 }
235 sub string { my ($i, $text) = @_;
236 bless({ m => [], nr => 0, l => 1, ll => length($text), i => $i,
237 t => $text }, 'nfa::string');
238 }
239 }
240  
241 my $IMP = $nfa::IMP;
242 my $NULL = $nfa::NULL;
243  
244 { package REbase;
245 }
246  
247 { package RE_ast; our @ISA = 'REbase';
248 sub nfa { my $self = shift; my $C = shift;
249 ::here();
250 $self->{'re'}->nfa($C);
251 }
252 }
253  
254 { package RE_assertion; our @ISA = 'REbase';
255 sub nfa { my ($self, $C) = @_;
256 if ($self->{assert} eq '?') {
257 my $re = $self->{re};
258 return nfa::seq($re->nfa($C), $IMP);
259 }
260 return $NULL;
261 }
262 }
263  
264 { package RE_assertvar; our @ISA = 'REbase';
265 sub nfa { $IMP }
266 }
267  
268 { package RE_block; our @ISA = 'REbase';
269 sub nfa { $IMP }
270 }
271  
272 { package RE_bindvar; our @ISA = 'REbase';
273 sub nfa { my $self = shift; my $C = shift; ::here();
274 $self->{'atom'}->nfa($C);
275 }
276 }
277  
278 { package RE_bindnamed; our @ISA = 'REbase';
279 sub nfa { my $self = shift; my $C = shift; ::here();
280 $self->{'atom'}->nfa($C);
281 }
282 }
283  
284 { package RE_bindpos; our @ISA = 'REbase';
285 sub nfa { my $self = shift; my $C = shift; ::here();
286 $self->{'atom'}->nfa($C);
287 }
288 }
289  
290 { package RE_bracket; our @ISA = 'REbase';
291 sub nfa { my $self = shift; my $C = shift; ::here();
292 $self->{'re'}->nfa($C);
293 }
294 }
295  
296 { package RE_cclass; our @ISA = 'REbase';
297 sub _get_char {
298 if ($_[0] =~ s/^([^\\])//s) { return ord($1) }
299 if ($_[0] =~ s/^\\n//) { return 10 }
300 if ($_[0] =~ s/^\\t//) { return 9 }
301 if ($_[0] =~ s/^\\x\{(.*?)\}//s) { return hex($1); }
302 if ($_[0] =~ s/^\\x(..)//s) { return hex($1); }
303 if ($_[0] =~ s/^\\(.)//s) { return ord($1) }
304  
305 return undef;
306 }
307  
308 sub nfa { my ($self, $C) = @_; ::here($self->{text});
309 $CursorBase::fakepos++;
310 my $cc = $self->{'text'};
311 Encode::_utf8_on($cc);
312 my ($neg, $text) = $cc =~ /^(-?)\[(.*)\]$/s;
313 die "whoops! $cc" unless defined $text;
314  
315 #XXX this ought to be pre parsed
316 my ($ch, $ch2);
317 my @chs;
318 while (1) {
319 $text =~ s/^\s+//;
320 if ($text =~ s/^\\s//) {
321 push @chs, 'Space/Y';
322 next;
323 }
324 if ($text =~ s/^\\w//) {
325 push @chs, '_', 'Gc/L', 'Gc/N';
326 next;
327 }
328 last if $text eq '';
329 $ch = _get_char($text);
330 if ($text =~ s/^\s*\.\.//) {
331 $ch2 = _get_char($text);
332 } else {
333 $ch2 = $ch;
334 }
335 push @chs, map { chr $_ } ($ch .. $ch2);
336 }
337  
338 if ($self->{i}) {
339 @chs = map { uc($_), lc($_) } @chs;
340 }
341  
342 $neg ? nfa::cclass(['ALL', @chs]) : nfa::cclass(map { [$_] } @chs);
343 }
344 }
345  
346 { package RE_decl; our @ISA = 'REbase';
347 sub nfa { $NULL }
348 }
349  
350 { package RE_double; our @ISA = 'REbase';
351 # XXX inadequate for "\n" without interpolation
352 sub nfa { my ($self, $C) = @_;
353 my $text = $self->{'text'};
354 Encode::_utf8_on($text);
355 ::here($text);
356 $STD::Cursor::fakepos++ if $text ne '';
357 my ($fixed, $imp);
358 if ( $text =~ /^(.*?)[\$\@\%\&\{]/ ) {
359 $fixed = $1; $imp = 1;
360 }
361 else {
362 $fixed = $text;
363 }
364 $fixed = nfa::string($self->{i}, $fixed);
365 $fixed = nfa::seq($fixed, $IMP) if $imp;
366 $fixed;
367 }
368 }
369  
370 { package RE_meta; our @ISA = 'REbase';
371 my %meta_nfa = (
372 # XXX I don't think these are quite right
373 '^' => $NULL, '^^' => $NULL, '$$' => $NULL, '$' => $NULL,
374 '«' => $NULL, '<<' => $NULL, '>>' => $NULL, '»' => $NULL,
375 # what?
376 '\\\\' => nfa::cclass(['\\']),
377 '\\"' => nfa::cclass(['"']),
378 '\\\'' => nfa::cclass(["'"]),
379 '\D' => nfa::cclass(['ALL', 'Gc/N']),
380 '\d' => nfa::cclass(['Gc/N']),
381 '\H' => nfa::cclass(['ALL', 'Perl/Blank']),
382 '\h' => nfa::cclass(['Perl/Blank'], ["\015"]),
383 '\N' => nfa::cclass(['ALL', "\n"]),
384 '\n' => nfa::cclass(["\n"]),
385 '\S' => nfa::cclass(['ALL', 'Space/Y']),
386 '\s' => nfa::cclass(['Space/Y']),
387 '\V' => nfa::cclass(['ALL', 'Perl/VertSpac']),
388 '\v' => nfa::cclass(['Perl/VertSpac']),
389 '\W' => nfa::cclass(['ALL', '_', 'Gc/L', 'Gc/N']),
390 '\w' => nfa::cclass(['_'], ['Gc/L'], ['Gc/N']),
391 '.' => nfa::cclass(['ALL']),
392 '::' => $IMP,
393 ':::' => $IMP,
394 '.*?' => $IMP,
395 '.*' => nfa::star(nfa::cclass(['ALL'])),
396 );
397  
398 sub nfa { my $self = shift; my ($C) = @_;
399 my $text = $self->{'text'};
400 Encode::_utf8_on($text);
401 ::here($text);
402 return $meta_nfa{$text} // die "unhandled meta $text";
403 }
404 }
405  
406 { package RE_method; our @ISA = 'REbase';
407 sub nfa { my ($self, $C) = @_;
408 my $name = $self->{'name'};
409 return $IMP if $self->{'rest'};
410 Encode::_utf8_on($name);
411 ::here($name);
412  
413 if ($name eq 'null' or $name eq 'ww') { return $NULL }
414 if ($name eq 'ws') { return $IMP; }
415 if ($name eq 'alpha') { $CursorBase::fakepos++; return nfa::cclass(['_'], ['Gc/L']); }
416 if ($name eq 'sym') {
417 $CursorBase::fakepos++;
418 my $sym = $self->{'sym'};
419 Encode::_utf8_on($sym);
420 return nfa::string($self->{i}, $sym);
421 }
422  
423 # XXX
424 $name = 'termish' if $name eq 'EXPR';
425  
426 my $mname = $name . '__PEEK';
427 my $lexer = $C->can($mname) ? $C->$mname()->{NFAT} : $IMP;
428 return nfa::method($name, $lexer);
429 }
430 }
431  
432 { package RE_method_internal; our @ISA = 'REbase';
433 sub nfa { $IMP }
434 }
435  
436 { package RE_method_re; our @ISA = 'REbase';
437 sub nfa { my ($self, $C) = @_;
438 my $name = $self->{name};
439 Encode::_utf8_on($name);
440 ::here($name);
441 my $re = $self->{re};
442 if ($name eq '') {
443 return $IMP;
444 } elsif ($name eq 'after') {
445 return $NULL;
446 } elsif ($name eq 'before') {
447 return nfa::seq($re->nfa($C), $IMP);
448 } else {
449 my $mname = $name . '__PEEK';
450 my $lexer = $C->can($mname) ? $C->$mname($re) : $IMP;
451 return nfa::method($name, $lexer->{NFAT});
452 }
453 }
454 }
455  
456 { package RE_noop; our @ISA = 'REbase';
457 sub nfa { $NULL }
458 }
459  
460 { package RE_every; our @ISA = 'REbase';
461 sub nfa { $IMP }
462 }
463  
464 { package RE_first; our @ISA = 'REbase';
465 sub nfa { my ($self, $C) = @_;
466 my $alts = $self->{'zyg'};
467 ::here(0+@$alts);
468 nfa::horizon($alts->[0]->nfa($C));
469 }
470 }
471  
472 { package RE_paren; our @ISA = 'REbase';
473 sub nfa { my $self = shift; my $C = shift; ::here();
474 $self->{'re'}->nfa($C);
475 }
476 }
477  
478 { package RE_quantified_atom; our @ISA = 'REbase';
479 sub nfa { my ($self, $C) = @_; ::here();
480 my $oldfakepos = $CursorBase::fakepos++;
481 my $subnfa = $self->{atom}->nfa($C);
482 #return $IMP if $self->{quant}[1]; XXX viv omits this currently
483 # XXX S05 is not quite clear; it could be read as saying to cut LTM
484 # *after* the atom
485 return $IMP if $self->{quant}[2]
486 && $self->{quant}[2]->isa('RE_block');
487  
488 my $k = $self->{quant}[0];
489 if ($k eq '?') {
490 return nfa::opt($subnfa);
491 } elsif ($k eq '*') {
492 return nfa::star($subnfa);
493 } elsif ($k eq '+') {
494 return nfa::seq($subnfa, nfa::star($subnfa));
495 } elsif ($k eq '**') {
496 my $subnfa2 = $self->{quant}[2]->nfa($C);
497 return nfa::seq($subnfa, nfa::star(nfa::seq($subnfa2, $subnfa)));
498 } else {
499 die "unknown quantifier $k";
500 }
501 }
502 }
503  
504 { package RE_qw; our @ISA = 'REbase';
505 sub nfa { my ($self, $C) = @_;
506 my $text = $self->{'text'};
507 Encode::_utf8_on($text);
508 ::here($text);
509 $CursorBase::fakepos++;
510 $text =~ s/^<\s*//;
511 $text =~ s/\s*>$//;
512  
513 nfa::horizon(nfa::ltm("", map { ["", nfa::string($self->{i}, $_)] } split(/\s+/, $text)));
514 }
515 }
516  
517 { package RE_sequence; our @ISA = 'REbase';
518 sub nfa { my ($self, $C) = @_; ::here;
519 my @zyg;
520 for my $k (@{ $self->{zyg} }) {
521 push @zyg, $k->nfa($C);
522 last if nfa::noreturn($zyg[-1]);
523 }
524 push @zyg, $NULL if !@zyg;
525 while (@zyg > 1) {
526 push @zyg, nfa::seq(splice(@zyg, -2, 2));
527 }
528 $zyg[0];
529 }
530 }
531  
532 { package RE_string; our @ISA = 'REbase';
533 sub nfa { my ($self, $C) = @_;
534 my $text = $self->{'text'};
535 Encode::_utf8_on($text);
536 ::here($text);
537 $CursorBase::fakepos++ if $text ne '';
538 nfa::string($self->{i}, $text);
539 }
540 }
541  
542 { package RE_submatch; our @ISA = 'REbase';
543 sub nfa { $IMP }
544 }
545  
546 { package RE_all; our @ISA = 'REbase';
547 sub nfa { $IMP }
548 }
549  
550 { package RE_any; our @ISA = 'REbase';
551 sub nfa { my $self = shift; my ($C) = @_;
552 my $alts = $self->{'zyg'};
553 ::here(0+@$alts);
554 my @outs;
555 my $oldfakepos = $CursorBase::fakepos;
556 my $minfakepos = $CursorBase::fakepos + 1;
557 my $ix = 0;
558  
559 for my $alt (@$alts) {
560 $CursorBase::fakepos = $oldfakepos;
561  
562 push @outs, [ $ix++, $alt->nfa($C) ];
563  
564 $minfakepos = $oldfakepos if $CursorBase::fakepos == $oldfakepos;
565 }
566 $CursorBase::fakepos = $minfakepos; # Did all branches advance?
567 nfa::ltm($self->{altname}, @outs);
568 }
569 }
570  
571 { package RE_var; our @ISA = 'REbase';
572 sub nfa { my ($self, $C) = @_;
573 my $var = $self->{var};
574 if (my $p = $C->_PARAMS) {
575 my $text = $p->{$var} || return $IMP;
576 $CursorBase::fakepos++ if length($text);
577 return nfa::string($self->{i}, $text);
578 }
579 return $IMP;
580 }
581 }
582  
583 1;