Corvus/Regex/Linear.pm

filter: Statementstmt 45.1% 143 / 317 Branchbran 31.2% 80 / 256 Conditioncond 38.5% 77 / 200 MC/DCmcdc 14.9% 16 / 107 Subroutinesub 64.7% 22 / 34 Podpod 0.0% 0 / 4 totaltotal 36.8% 338 / 918 CC 210 SCAR 55.1
CC
210
Cov
39%
_ways
870.0
_visit
499.9
_fails_within
217.8
CRAP 246.3
« Corvus/Collecting.pm ↑ Summary Corvus/CodeGen.pm »
1 package JSON::Schema::Corvus::Regex::Linear;
2  
3 # Proves that a backtracking engine (Perl's) matches a pattern in time proportional to the text, whatever the text is:
4 # a port of the Python package's _Linear, over the syntax tree of Regex::Parse. Perl's engine cannot be stopped once a
5 # match has started, so with the limit of a match in force it is given the patterns this proves and no others; every
6 # other pattern goes to the matcher of Regex::Vm, which keeps a limit.
7 #
8 # The engine tries one way through a pattern and goes back to the last choice when it fails. The proof is that no text
9 # makes it go over more than a bounded number of characters a second time. It holds when, at every choice (the
10 # alternatives of an alternation, one more iteration of a repetition or none), the next character of the text says
11 # which way to go: the sets of characters that the ways can start with, or that can follow the choice where a way can
12 # match nothing, have no character in common, and at most one way can match nothing. A way that is not taken then fails
13 # at its first character. The body of a repetition has to take a character.
14 #
15 # Some things are allowed beyond that, each for a bounded cost, whose product (factor) times the nodes a character can
16 # pass more than once bounds the work for a character of the text (see the Python package's pattern.py for each):
17 # a bounded pattern with no lookahead and few ways through it; a repetition whose end the next character does not
18 # decide, when what follows can take w characters at most and still fail; alternatives that start alike but take a
19 # bounded number of characters; a bounded lookahead anywhere, and an unbounded one at the start of a pattern that starts
20 # with ^; and a pattern that does not start with ^ when a try that fails takes w characters at most.
21 #
22 # A pattern with a backreference, a lookbehind, or a case-insensitive word boundary is not proved.
23  
24 4 ▶use 5.026;
Subroutine BEGIN: called CC=1 SCAR=0.0
25 4 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
26 4 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
27 4 ▶use List::Util ();
Subroutine BEGIN: called CC=1 SCAR=0.0
28 4 ▶use Scalar::Util ();
Subroutine BEGIN: called CC=1 SCAR=0.0
29  
30 4 ▶use constant { MAX_FACTOR => 64, MAX_WORK => 4096, MAX_WAYS => 256, MAX_WAYS_WORK => 1024, INFINITE => 9**9**9 };
Subroutine BEGIN: called CC=1 SCAR=0.0
31 4 ▶use constant EVERY => [0, 0x10FFFF];
Subroutine BEGIN: called CC=1 SCAR=0.0
32  
33 # --- Sets of characters, as flat lists of inclusive bounds ---
34  
35 12 ▶sub _merged {
Subroutine _merged: called CC=5 SCAR=16.1
36 12 my ($ranges) = @_;
37 12 my @order = sort { $ranges->[2 * $a] <=> $ranges->[2 * $b] } 0 .. @$ranges / 2 - 1;
38 12 my @out;
39 12 for my $i (@order) {
40 29 my ($lo, $hi) = ($ranges->[2 * $i], $ranges->[2 * $i + 1]);
41 29 ▶ if (@out && $lo <= $out[-1] + 1) {
Branch: 1 branch
BranchTrueFalseTotal
if (@out and $lo <= $out[-1] + 1) 4 25 29
Condition100%3/3
@out and $lo <= $out[-1] + 1
!ll&&!rl&&r
10154
MC/DC100%2/2
@out and $lo <= $out[-1] + 1
@out $lo <= $out[-1] + 1
Truth table100%3/3
A and B
A= @outB= $lo <= $out[-1] + 1
ABresult
0X0
100
111
42 4 ▶ $out[-1] = $hi if $hi > $out[-1];
Branch: 1 branch
BranchTrueFalseTotal
if $hi > $out[-1] 4 0 4
43 4 next;
44 }
45 25 push @out, $lo, $hi;
46 }
47 12 return \@out;
48 }
49  
50 # Whether two merged sets have a character in common.
51 3 ▶sub _meet {
Subroutine _meet: called CC=5 SCAR=16.4
52 3 my ($a, $b) = @_;
53 3 my ($i, $j) = (0, 0);
54 3 ▶ while ($i < @$a && $j < @$b) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < @$a and $j < @$b) 2 3 5
Condition66%2/3
$i < @$a and $j < @$b
!ll&&!rl&&r
032
MC/DC50%1/2
$i < @$a and $j < @$b
$i < @$a $j < @$b
Truth table66%2/3
A and B
A= $i < @$aB= $j < @$b
ABresult
0X0
100
111
55 2 ▶ if ($a->[$i + 1] < $b->[$j]) { $i += 2 }
Branch: 2 branches
BranchTrueFalseTotal
if ($$a[$i + 1] < $b->[$j]) { } 1 1 2
elsif ($$b[$j + 1] < $a->[$i]) { } 1 0 1
56 1 elsif ($b->[$j + 1] < $a->[$i]) { $j += 2 }
57 0 else { return 1 }
58 }
59 3 return 0;
60 }
61  
62 # --- Facts about nodes ---
63  
64 24 ▶sub _zero_width {
Subroutine _zero_width: called CC=6 SCAR=18.7
65 24 my ($k) = @_;
66 24 ▶ return $k eq 'bol' || $k eq 'eol' || $k eq 'line_start' || $k eq 'line_end' || $k eq 'wb' || $k eq 'nwb';
Condition73%11/15
$k eq 'bol' || $k eq 'eol' || $k eq 'line_start' || $k eq 'line_end' || $k eq 'wb' || $k eq 'nwb'
l!l&&r!l&&!r
14010
$k eq "bol" or $k eq "eol" or $k eq "line_start" or $k eq "line_end" or $k eq "wb"
l!l&&r!l&&!r
14010
$k eq "bol" or $k eq "eol" or $k eq "line_start" or $k eq "line_end"
l!l&&r!l&&!r
14010
$k eq "bol" or $k eq "eol" or $k eq "line_start"
l!l&&r!l&&!r
14010
$k eq "bol" or $k eq "eol"
l!l&&r!l&&!r
6810
MC/DC33%2/6
$k eq 'bol' || $k eq 'eol' || $k eq 'line_start' || $k eq 'line_end' || $k eq 'wb' || $k eq 'nwb'
$k eq "bol" $k eq "eol" $k eq "line_start" $k eq "line_end" $k eq "wb" $k eq 'nwb'
Truth table42%3/7
A or B or C or D or E || F
A= $k eq "bol"B= $k eq "eol"C= $k eq "line_start"D= $k eq "line_end"E= $k eq "wb"F= $k eq 'nwb'
ABCDEFresult
1XXXXX1
01XXXX1
001XXX1
0001XX1
00001X1
0000011
0000000
67 }
68  
69 # Whether the node can match without taking a character (it may say yes for one that cannot).
70 11 ▶sub matches_nothing {
Subroutine matches_nothing: called CC=12 SCAR=33.5
Pod undocumented
71 11 my ($n) = @_;
72 11 ▶ return $n->{_nothing} //= do {
Condition33%1/3
$n->{"_nothing"} //= do { my $k = $n->{"kind"}; $k eq "char" || $k eq "set" ? 0 : ($k eq "cat" ? &List::Util::all(sub { matches_nothing($_); } , @{$$n{"subs"};}) ? 1 : 0 : ($k eq "alt" ? &List::Util::any(sub { matches_nothing($_); } , @{$$n{"subs"};}) ? 1 : 0 : ($k eq "group" ? matches_nothing($n->{"subs"}[0]) : ($k eq "repeat" ? $n->{"min"} == 0 || matches_nothing($n->{"subs"}[0]) ? 1 : 0 : 1)))) }
l!l&&r!l&&!r
0110
MC/DC0%0/2
$n->{"_nothing"} //= do { my $k = $n->{"kind"}; $k eq "char" || $k eq "set" ? 0 : ($k eq "cat" ? &List::Util::all(sub { matches_nothing($_); } , @{$$n{"subs"};}) ? 1 : 0 : ($k eq "alt" ? &List::Util::any(sub { matches_nothing($_); } , @{$$n{"subs"};}) ? 1 : 0 : ($k eq "group" ? matches_nothing($n->{"subs"}[0]) : ($k eq "repeat" ? $n->{"min"} == 0 || matches_nothing($n->{"subs"}[0]) ? 1 : 0 : 1)))) }
$n->{"_nothing"} do { my $k = $n->{"kind"}; $k eq "char" || $k eq "set" ? 0 : ($k eq "cat" ? &List::Util::all(sub { matches_nothing($_); } , @{$$n{"subs"};}) ? 1 : 0 : ($k eq "alt" ? &List::Util::any(sub { matches_nothing($_); } , @{$$n{"subs"};}) ? 1 : 0 : ($k eq "group" ? matches_nothing($n->{"subs"}[0]) : ($k eq "repeat" ? $n->{"min"} == 0 || matches_nothing($n->{"subs"}[0]) ? 1 : 0 : 1)))) }
Truth table33%1/3
A //= B
A= $n->{"_nothing"}B= do { my $k = $n->{"kind"}; $k eq "char" || $k eq "set" ? 0 : ($k eq "cat" ? &List::Util::all(sub { matches_nothing($_); } , @{$$n{"subs"};}) ? 1 : 0 : ($k eq "alt" ? &List::Util::any(sub { matches_nothing($_); } , @{$$n{"subs"};}) ? 1 : 0 : ($k eq "group" ? matches_nothing($n->{"subs"}[0]) : ($k eq "repeat" ? $n->{"min"} == 0 || matches_nothing($n->{"subs"}[0]) ? 1 : 0 : 1)))) }
ABresult
1X1
011
000
73 11 my $k = $n->{kind};
74 $k eq 'char' || $k eq 'set' ? 0
75 0 ▶ : $k eq 'cat' ? (List::Util::all { matches_nothing($_) } @{ $n->{subs} }) ? 1 : 0
Subroutine __ANON__: not called CC=1 SCAR=4.6
Branch: 2 branches
BranchTrueFalseTotal
$k eq 'alt' ? : 0 7 7
&List::Util::any(sub { matches_nothing($_); } , @{$$n{'subs'};}) ? : 0 0 0
76 0 ▶ : $k eq 'alt' ? (List::Util::any { matches_nothing($_) } @{ $n->{subs} }) ? 1 : 0
Subroutine __ANON__: not called CC=1 SCAR=1.5
Branch: 3 branches
BranchTrueFalseTotal
$k eq 'group' ? : 0 7 7
$k eq 'repeat' ? : 3 4 7
$n->{'min'} == 0 || matches_nothing($n->{'subs'}[0]) ? : 3 0 3
Condition33%1/3
$n->{"min"} == 0 or matches_nothing($n->{"subs"}[0])
l!l&&r!l&&!r
300
MC/DC0%0/2
$n->{"min"} == 0 or matches_nothing($n->{"subs"}[0])
$n->{"min"} == 0 matches_nothing($n->{"subs"}[0])
Truth table33%1/3
A or B
A= $n->{"min"} == 0B= matches_nothing($n->{"subs"}[0])
ABresult
1X1
011
000
77 : $k eq 'group' ? matches_nothing($n->{subs}[0])
78 11 ▶ : $k eq 'repeat' ? ($n->{min} == 0 || matches_nothing($n->{subs}[0])) ? 1 : 0
Branch: 3 branches
BranchTrueFalseTotal
$k eq 'char' || $k eq 'set' ? : 4 7 11
$k eq 'cat' ? : 0 7 7
&List::Util::all(sub { matches_nothing($_); } , @{$$n{'subs'};}) ? : 0 0 0
Condition100%3/3
$k eq "char" or $k eq "set"
l!l&&r!l&&!r
137
MC/DC100%2/2
$k eq "char" or $k eq "set"
$k eq "char" $k eq "set"
Truth table100%3/3
A or B
A= $k eq "char"B= $k eq "set"
ABresult
1X1
011
000
79 : 1;
80 };
81 }
82  
83 # Whether the node matches nothing wherever it matches: it has assertions and lookarounds, and nothing that takes a
84 # character.
85 3 ▶sub only_nothing {
Subroutine only_nothing: called CC=11 SCAR=42.5
Pod undocumented
86 3 my ($n) = @_;
87 3 my $k = $n->{kind};
88 3 ▶ return 0 if $k eq 'char' || $k eq 'set' || $k eq 'backref';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "char" or $k eq "set" or $k eq "backref" 3 0 3
Condition50%3/6
$k eq "char" or $k eq "set" or $k eq "backref"
l!l&&r!l&&!r
300
$k eq "char" or $k eq "set"
l!l&&r!l&&!r
120
MC/DC0%0/3
$k eq "char" or $k eq "set" or $k eq "backref"
$k eq "char" $k eq "set" $k eq "backref"
Truth table50%2/4
A or B or C
A= $k eq "char"B= $k eq "set"C= $k eq "backref"
ABCresult
1XX1
01X1
0011
0000
89 0 ▶ return 1 if $k eq 'look' || $k eq 'empty' || _zero_width($k);
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "look" or $k eq "empty" or _zero_width($k) 0 0 0
Condition0%0/6
$k eq "look" or $k eq "empty" or _zero_width($k)
l!l&&r!l&&!r
000
$k eq "look" or $k eq "empty"
l!l&&r!l&&!r
000
MC/DC0%0/3
$k eq "look" or $k eq "empty" or _zero_width($k)
$k eq "look" $k eq "empty" _zero_width($k)
Truth table0%0/4
A or B or C
A= $k eq "look"B= $k eq "empty"C= _zero_width($k)
ABCresult
1XX1
01X1
0011
0000
90 0 ▶ return $n->{max} == 0 || only_nothing($n->{subs}[0]) ? 1 : 0 if $k eq 'repeat';
Branch: 2 branches
BranchTrueFalseTotal
if $k eq "repeat" 0 0 0
$n->{'max'} == 0 || only_nothing($n->{'subs'}[0]) ? : 0 0 0
Condition0%0/3
$n->{"max"} == 0 or only_nothing($n->{"subs"}[0])
l!l&&r!l&&!r
000
MC/DC0%0/2
$n->{"max"} == 0 or only_nothing($n->{"subs"}[0])
$n->{"max"} == 0 only_nothing($n->{"subs"}[0])
Truth table0%0/3
A or B
A= $n->{"max"} == 0B= only_nothing($n->{"subs"}[0])
ABresult
1X1
011
000
91 0 ▶ return (List::Util::all { only_nothing($_) } @{ $n->{subs} }) ? 1 : 0;
Subroutine __ANON__: not called CC=1 SCAR=6.9
Branch: 1 branch
BranchTrueFalseTotal
&List::Util::all(sub { only_nothing($_); } , @{$$n{'subs'};}) ? : 0 0 0
92 }
93  
94 2 ▶sub new {
Subroutine new: called CC=1 SCAR=0.0
Pod undocumented
95 2 my ($class) = @_;
96 2 return bless { factor => 1, nodes => 0, repeated => 0, once => {} }, $class;
97 }
98  
99 0 ▶sub _not_linear { die "not linear\n" }
Subroutine _not_linear: not called CC=1 SCAR=6.9
100  
101 # Whether the pattern (its tree, after Regex::Vm's simplify) is proved.
102 2 ▶sub proves {
Subroutine proves: called CC=13 SCAR=39.9
Pod undocumented
103 2 my ($self, $root) = @_;
104 2 my ($anchored, $bounded);
105 2 my $ok = eval {
106 2 $anchored = $self->_anchored($root);
107 2 ▶ if ($self->_bounded($root, $anchored)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($self->_bounded($root, $anchored)) 0 2 2
108 0 $bounded = 1;
109 0 return 1;
110 }
111 2 ▶ if ($anchored) {
Branch: 1 branch
BranchTrueFalseTotal
if ($anchored) { } 2 0 2
112 2 $self->_mark_once($root);
113 }
114 else {
115 0 my $top = $root;
116 0 ▶ $top = $top->{subs}[0] while $top->{kind} eq 'group';
Branch: 1 branch
BranchTrueFalseTotal
$top->{"kind"} eq "group" and do { $top = $top->{"subs"}[0] } 0 0 0
117 # An alternative that starts with ^ fails at once everywhere but at the start of the text.
118 0 ▶ my @ways = $top->{kind} eq 'alt' ? @{ $top->{subs} } : ($top);
Branch: 1 branch
BranchTrueFalseTotal
$top->{'kind'} eq 'alt' ? : 0 0 0
119 0 my $widest = 0;
120 0 for my $x (@ways) {
121 0 ▶ next if $self->_anchored($x);
Branch: 1 branch
BranchTrueFalseTotal
if $self->_anchored($x) 0 0 0
122 0 my $w = $self->_fails_within($x, 1);
123 0 ▶ $widest = $w if $w > $widest;
Branch: 1 branch
BranchTrueFalseTotal
if $w > $widest 0 0 0
124 }
125 0 $self->_cost($widest);
126 }
127 2 $self->_visit($root, [], 1, 0, 1, 1);
128 2 1;
129 };
130 2 ▶ if (!defined $ok) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $ok) 0 2 2
131 0 ▶ return 0 if $@ eq "not linear\n";
Branch: 1 branch
BranchTrueFalseTotal
if $@ eq "not linear\n" 0 0 0
132 0 die $@;
133 }
134 2 ▶ return 1 if $bounded;
Branch: 1 branch
BranchTrueFalseTotal
if $bounded 0 2 2
135 2 ▶ return $self->{factor} * ($anchored ? $self->{repeated} : $self->{nodes}) <= MAX_WORK ? 1 : 0;
Branch: 2 branches
BranchTrueFalseTotal
$self->{'factor'} * ($anchored ? $self->{'repeated'} : $self->{'nodes'}) <= 4096 ? : 2 0 2
$anchored ? : 2 0 2
136 }
137  
138 0 ▶sub _cost {
Subroutine _cost: not called CC=2 SCAR=17.9
139 0 my ($self, $width) = @_;
140 0 $self->{factor} *= 1 + $width;
141 0 ▶ _not_linear() if $self->{factor} > MAX_FACTOR;
Branch: 1 branch
BranchTrueFalseTotal
if $self->{"factor"} > 64 0 0 0
142 }
143  
144 # Whether the pattern takes a bounded number of characters, has no lookahead, and has few ways through it.
145 2 ▶sub _bounded {
Subroutine _bounded: called CC=6 SCAR=31.0
146 2 my ($self, $root, $anchored) = @_;
147 2 ▶ return 0 if $self->_length($root) > MAX_WORK || _has_look($root);
Branch: 1 branch
BranchTrueFalseTotal
if $self->_length($root) > 4096 or _has_look($root) 2 0 2
Condition33%1/3
$self->_length($root) > 4096 or _has_look($root)
l!l&&r!l&&!r
200
MC/DC0%0/2
$self->_length($root) > 4096 or _has_look($root)
$self->_length($root) > 4096 _has_look($root)
Truth table33%1/3
A or B
A= $self->_length($root) > 4096B= _has_look($root)
ABresult
1X1
011
000
148 0 ▶ my $ways = $self->_ways($root) or return 0;
Branch: 1 branch
BranchTrueFalseTotal
my $ways = $self->_ways($root) or return 0 0 0 0
149 0 my $work = List::Util::sum(0, map { @$_ + 1 } @$ways);
150 0 ▶ return $work <= ($anchored ? MAX_WORK : MAX_WAYS_WORK) ? 1 : 0;
Branch: 2 branches
BranchTrueFalseTotal
$work <= ($anchored ? 4096 : 1024) ? : 0 0 0
$anchored ? : 0 0 0
151 }
152  
153 0 ▶sub _has_look {
Subroutine _has_look: not called CC=5 SCAR=34.0
154 0 my ($n) = @_;
155 0 ▶ return 1 if $n->{kind} eq 'look' || $n->{kind} eq 'backref';
Branch: 1 branch
BranchTrueFalseTotal
if $n->{"kind"} eq "look" or $n->{"kind"} eq "backref" 0 0 0
Condition0%0/3
$n->{"kind"} eq "look" or $n->{"kind"} eq "backref"
l!l&&r!l&&!r
000
MC/DC0%0/2
$n->{"kind"} eq "look" or $n->{"kind"} eq "backref"
$n->{"kind"} eq "look" $n->{"kind"} eq "backref"
Truth table0%0/3
A or B
A= $n->{"kind"} eq "look"B= $n->{"kind"} eq "backref"
ABresult
1X1
011
000
156 0 ▶ return (List::Util::any { _has_look($_) } @{ $n->{subs} // [] }) ? 1 : 0;
Subroutine __ANON__: not called CC=1 SCAR=6.9
Branch: 1 branch
BranchTrueFalseTotal
&List::Util::any(sub { _has_look($_); } , @{$n->{'subs'} // [];}) ? : 0 0 0
Condition0%0/2
$n->{"subs"} // []
l!l
00
MC/DC0%0/1
$n->{"subs"} // []
$n->{"subs"}
Truth table0%0/2
A
A= $n->{"subs"}
Aresult
11
00
157 }
158  
159 # The ways through a node that takes a bounded number of characters, each as the sets of characters it takes in order.
160 # undef: there are too many, or no bound.
161 0 ▶sub _ways {
Subroutine _ways: not called CC=29 SCAR=67.7
162 0 my ($self, $n) = @_;
163 0 my $k = $n->{kind};
164 0 ▶ return [ [ $self->_first($n) ] ] if $k eq 'char' || $k eq 'set';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "char" or $k eq "set" 0 0 0
Condition0%0/3
$k eq "char" or $k eq "set"
l!l&&r!l&&!r
000
MC/DC0%0/2
$k eq "char" or $k eq "set"
$k eq "char" $k eq "set"
Truth table0%0/3
A or B
A= $k eq "char"B= $k eq "set"
ABresult
1X1
011
000
165 0 ▶ return [ [] ] if $k eq 'empty' || $k eq 'look' || _zero_width($k);
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "empty" or $k eq "look" or _zero_width($k) 0 0 0
Condition0%0/6
$k eq "empty" or $k eq "look" or _zero_width($k)
l!l&&r!l&&!r
000
$k eq "empty" or $k eq "look"
l!l&&r!l&&!r
000
MC/DC0%0/3
$k eq "empty" or $k eq "look" or _zero_width($k)
$k eq "empty" $k eq "look" _zero_width($k)
Truth table0%0/4
A or B or C
A= $k eq "empty"B= $k eq "look"C= _zero_width($k)
ABCresult
1XX1
01X1
0011
0000
166 0 ▶ return undef if $k eq 'backref';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "backref" 0 0 0
167 0 ▶ return $self->_ways($n->{subs}[0]) if $k eq 'group';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "group" 0 0 0
168 0 ▶ if ($k eq 'alt') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "alt") 0 0 0
169 0 my @out;
170 0 for my $x (@{ $n->{subs} }) {
171 0 my $more = $self->_ways($x);
172 0 ▶ return undef if !$more || @out + @$more > MAX_WAYS;
Branch: 1 branch
BranchTrueFalseTotal
if not $more or @out + @$more > 256 0 0 0
Condition0%0/3
not $more or @out + @$more > 256
l!l&&r!l&&!r
000
MC/DC0%0/2
not $more or @out + @$more > 256
not $more @out + @$more > 256
Truth table0%0/3
not(A) or B
A= not $moreB= @out + @$more > 256
ABresult
1X1
011
000
173 0 push @out, @$more;
174 }
175 0 return \@out;
176 }
177 0 ▶ if ($k eq 'cat') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "cat") 0 0 0
178 0 my @out = ([]);
179 0 for my $x (@{ $n->{subs} }) {
180 0 my $more = $self->_ways($x);
181 0 ▶ return undef if !$more || @out * @$more > MAX_WAYS;
Branch: 1 branch
BranchTrueFalseTotal
if not $more or @out * @$more > 256 0 0 0
Condition0%0/3
not $more or @out * @$more > 256
l!l&&r!l&&!r
000
MC/DC0%0/2
not $more or @out * @$more > 256
not $more @out * @$more > 256
Truth table0%0/3
not(A) or B
A= not $moreB= @out * @$more > 256
ABresult
1X1
011
000
182 0 ▶ next if @$more == 1 && !@{ $more->[0] };
Branch: 1 branch
BranchTrueFalseTotal
if @$more == 1 and not @{$more->[0];} 0 0 0
Condition0%0/3
@$more == 1 and not @{$more->[0];}
!ll&&!rl&&r
000
MC/DC0%0/2
@$more == 1 and not @{$more->[0];}
@$more == 1 not @{$more->[0];}
Truth table0%0/3
A and not(B)
A= @$more == 1B= not @{$more->[0];}
ABresult
0X0
100
111
183 0 @out = map { my $a = $_; map { [ @$a, @$_ ] } @$more } @out;
184 }
185 0 return \@out;
186 }
187 # A repetition.
188 0 ▶ return [ [] ] if $n->{max} == 0 || only_nothing($n->{subs}[0]);
Branch: 1 branch
BranchTrueFalseTotal
if $n->{"max"} == 0 or only_nothing($n->{"subs"}[0]) 0 0 0
Condition0%0/3
$n->{"max"} == 0 or only_nothing($n->{"subs"}[0])
l!l&&r!l&&!r
000
MC/DC0%0/2
$n->{"max"} == 0 or only_nothing($n->{"subs"}[0])
$n->{"max"} == 0 only_nothing($n->{"subs"}[0])
Truth table0%0/3
A or B
A= $n->{"max"} == 0B= only_nothing($n->{"subs"}[0])
ABresult
1X1
011
000
189 0 ▶ return undef if $n->{max} == -1 || $n->{max} > MAX_WAYS;
Branch: 1 branch
BranchTrueFalseTotal
if $n->{"max"} == -1 or $n->{"max"} > 256 0 0 0
Condition0%0/3
$n->{"max"} == -1 or $n->{"max"} > 256
l!l&&r!l&&!r
000
MC/DC0%0/2
$n->{"max"} == -1 or $n->{"max"} > 256
$n->{"max"} == -1 $n->{"max"} > 256
Truth table0%0/3
A or B
A= $n->{"max"} == -1B= $n->{"max"} > 256
ABresult
1X1
011
000
190 0 ▶ my $body = $self->_ways($n->{subs}[0]) or return undef;
Branch: 1 branch
BranchTrueFalseTotal
my $body = $self->_ways($n->{"subs"}[0]) or return undef 0 0 0
191 0 my @out;
192 0 my @some = ([]);
193 0 for my $count (0 .. $n->{max}) {
194 0 ▶ if ($count >= $n->{min}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($count >= $n->{"min"}) 0 0 0
195 0 ▶ return undef if @out + @some > MAX_WAYS;
Branch: 1 branch
BranchTrueFalseTotal
if @out + @some > 256 0 0 0
196 0 push @out, @some;
197 }
198 0 ▶ if ($count < $n->{max}) {
Branch: 1 branch
BranchTrueFalseTotal
if ($count < $n->{"max"}) 0 0 0
199 0 ▶ return undef if @some * @$body > MAX_WAYS || @{ $some[0] } > MAX_WAYS;
Branch: 1 branch
BranchTrueFalseTotal
if @some * @$body > 256 or @{$some[0];} > 256 0 0 0
Condition0%0/3
@some * @$body > 256 or @{$some[0];} > 256
l!l&&r!l&&!r
000
MC/DC0%0/2
@some * @$body > 256 or @{$some[0];} > 256
@some * @$body > 256 @{$some[0];} > 256
Truth table0%0/3
A or B
A= @some * @$body > 256B= @{$some[0];} > 256
ABresult
1X1
011
000
200 0 @some = map { my $a = $_; map { [ @$a, @$_ ] } @$body } @some;
201 }
202 }
203 0 return \@out;
204 }
205  
206 # Whether some text that one way takes can start with a text that the other takes.
207 0 ▶sub _starts_with {
Subroutine _starts_with: not called CC=4 SCAR=30.0
208 0 my ($a, $b) = @_;
209 0 ▶ my $n = @$a < @$b ? @$a : @$b;
Branch: 1 branch
BranchTrueFalseTotal
@$a < @$b ? : 0 0 0
210 0 for my $i (0 .. $n - 1) {
211 0 ▶ return 0 unless _meet($a->[$i], $b->[$i]);
Branch: 1 branch
BranchTrueFalseTotal
unless _meet($a->[$i], $b->[$i]) 0 0 0
212 }
213 0 return 1;
214 }
215  
216 # The characters the text that the node matches can start with.
217 14 ▶sub _first {
Subroutine _first: called CC=13 SCAR=31.8
218 14 my ($self, $n) = @_;
219 14 ▶ return $n->{_first} //= do {
Condition66%2/3
$n->{"_first"} //= do { my $k = $n->{"kind"}; if ($k eq "char") { [$n->{"r"}, $n->{"r"}]; } elsif ($k eq "set") { [@{$n->{"set"}{"ranges"};}]; } elsif ($k eq "cat") { my @parts; foreach my $x (@{$$n{"subs"};}) { push @parts, @{$self->_first($x);}; last unless matches_nothing($x); } ; _merged(\@parts); } elsif ($k eq "look" or $k eq "backref" or $k eq "empty" or _zero_width($k) or $k eq "repeat" and $n->{"max"} == 0) { []; } else { _merged([map({@{$self->_first($_);};} @{$$n{"subs"};})]); } }
l!l&&r!l&&!r
3110
MC/DC0%0/2
$n->{"_first"} //= do { my $k = $n->{"kind"}; if ($k eq "char") { [$n->{"r"}, $n->{"r"}]; } elsif ($k eq "set") { [@{$n->{"set"}{"ranges"};}]; } elsif ($k eq "cat") { my @parts; foreach my $x (@{$$n{"subs"};}) { push @parts, @{$self->_first($x);}; last unless matches_nothing($x); } ; _merged(\@parts); } elsif ($k eq "look" or $k eq "backref" or $k eq "empty" or _zero_width($k) or $k eq "repeat" and $n->{"max"} == 0) { []; } else { _merged([map({@{$self->_first($_);};} @{$$n{"subs"};})]); } }
$n->{"_first"} do { my $k = $n->{"kind"}; if ($k eq "char") { [$n->{"r"}, $n->{"r"}]; } elsif ($k eq "set") { [@{$n->{"set"}{"ranges"};}]; } elsif ($k eq "cat") { my @parts; foreach my $x (@{$$n{"subs"};}) { push @parts, @{$self->_first($x);}; last unless matches_nothing($x); } ; _merged(\@parts); } elsif ($k eq "look" or $k eq "backref" or $k eq "empty" or _zero_width($k) or $k eq "repeat" and $n->{"max"} == 0) { []; } else { _merged([map({@{$self->_first($_);};} @{$$n{"subs"};})]); } }
Truth table66%2/3
A //= B
A= $n->{"_first"}B= do { my $k = $n->{"kind"}; if ($k eq "char") { [$n->{"r"}, $n->{"r"}]; } elsif ($k eq "set") { [@{$n->{"set"}{"ranges"};}]; } elsif ($k eq "cat") { my @parts; foreach my $x (@{$$n{"subs"};}) { push @parts, @{$self->_first($x);}; last unless matches_nothing($x); } ; _merged(\@parts); } elsif ($k eq "look" or $k eq "backref" or $k eq "empty" or _zero_width($k) or $k eq "repeat" and $n->{"max"} == 0) { []; } else { _merged([map({@{$self->_first($_);};} @{$$n{"subs"};})]); } }
ABresult
1X1
011
000
220 11 my $k = $n->{kind};
221 11 ▶ if ($k eq 'char') { [ $n->{r}, $n->{r} ] }
Branch: 4 branches
BranchTrueFalseTotal
if ($k eq 'char') { } 1 10 11
elsif ($k eq 'set') { } 3 7 10
elsif ($k eq 'cat') { } 0 7 7
elsif ($k eq 'look' or $k eq 'backref' or $k eq 'empty' or _zero_width($k) or $k eq 'repeat' and $n->{'max'} == 0) { } 4 3 7
222 3 elsif ($k eq 'set') { [ @{ $n->{set}{ranges} } ] }
223 elsif ($k eq 'cat') {
224 0 my @parts;
225 0 for my $x (@{ $n->{subs} }) {
226 0 push @parts, @{ $self->_first($x) };
227 0 ▶ last unless matches_nothing($x);
Branch: 1 branch
BranchTrueFalseTotal
unless matches_nothing($x) 0 0 0
228 }
229 0 _merged(\@parts);
230 }
231 ▶ elsif ($k eq 'look' || $k eq 'backref' || $k eq 'empty' || _zero_width($k) || ($k eq 'repeat' && $n->{max} == 0)) {
Condition46%7/15
$k eq "look" or $k eq "backref" or $k eq "empty" or _zero_width($k) or $k eq "repeat" and $n->{"max"} == 0
l!l&&r!l&&!r
403
$k eq "look" or $k eq "backref" or $k eq "empty" or _zero_width($k)
l!l&&r!l&&!r
043
$k eq "look" or $k eq "backref" or $k eq "empty"
l!l&&r!l&&!r
007
$k eq "look" or $k eq "backref"
l!l&&r!l&&!r
007
$k eq "repeat" and $n->{"max"} == 0
!ll&&!rl&&r
030
MC/DC16%1/6
$k eq "look" or $k eq "backref" or $k eq "empty" or _zero_width($k) or $k eq "repeat" and $n->{"max"} == 0
$k eq "look" $k eq "backref" $k eq "empty" _zero_width($k) $k eq "repeat" $n->{"max"} == 0
Truth table28%2/7
A or B or C or D or E and F
A= $k eq "look"B= $k eq "backref"C= $k eq "empty"D= _zero_width($k)E= $k eq "repeat"F= $n->{"max"} == 0
ABCDEFresult
1XXXXX1
01XXXX1
001XXX1
0001XX1
0000111
00000X0
0000100
232 4 [];
233 }
234 else {
235 3 _merged([ map { @{ $self->_first($_) } } @{ $n->{subs} } ]);
236 }
237 };
238 }
239  
240 # The most characters the node can take.
241 19 ▶sub _length {
Subroutine _length: called CC=13 SCAR=28.5
242 19 my ($self, $n) = @_;
243 19 ▶ return $n->{_length} //= do {
Condition66%2/3
$n->{"_length"} //= do { my $k = $n->{"kind"}; if ($k eq "char" or $k eq "set") { 1; } elsif ($k eq "look" or $k eq "backref" or $k eq "empty" or _zero_width($k)) { 0; } elsif ($k eq "alt") { &List::Util::max(map({$self->_length($_);} @{$$n{"subs"};})); } elsif ($k eq "repeat") { my $body = $self->_length($n->{"subs"}[0]); $n->{"max"} == 0 || $body == 0 ? 0 : ($n->{"max"} == -1 ? "Inf" : $n->{"max"} * $body); } else { &List::Util::sum(0, map({$self->_length($_);} @{$$n{"subs"};})); } }
l!l&&r!l&&!r
6130
MC/DC0%0/2
$n->{"_length"} //= do { my $k = $n->{"kind"}; if ($k eq "char" or $k eq "set") { 1; } elsif ($k eq "look" or $k eq "backref" or $k eq "empty" or _zero_width($k)) { 0; } elsif ($k eq "alt") { &List::Util::max(map({$self->_length($_);} @{$$n{"subs"};})); } elsif ($k eq "repeat") { my $body = $self->_length($n->{"subs"}[0]); $n->{"max"} == 0 || $body == 0 ? 0 : ($n->{"max"} == -1 ? "Inf" : $n->{"max"} * $body); } else { &List::Util::sum(0, map({$self->_length($_);} @{$$n{"subs"};})); } }
$n->{"_length"} do { my $k = $n->{"kind"}; if ($k eq "char" or $k eq "set") { 1; } elsif ($k eq "look" or $k eq "backref" or $k eq "empty" or _zero_width($k)) { 0; } elsif ($k eq "alt") { &List::Util::max(map({$self->_length($_);} @{$$n{"subs"};})); } elsif ($k eq "repeat") { my $body = $self->_length($n->{"subs"}[0]); $n->{"max"} == 0 || $body == 0 ? 0 : ($n->{"max"} == -1 ? "Inf" : $n->{"max"} * $body); } else { &List::Util::sum(0, map({$self->_length($_);} @{$$n{"subs"};})); } }
Truth table66%2/3
A //= B
A= $n->{"_length"}B= do { my $k = $n->{"kind"}; if ($k eq "char" or $k eq "set") { 1; } elsif ($k eq "look" or $k eq "backref" or $k eq "empty" or _zero_width($k)) { 0; } elsif ($k eq "alt") { &List::Util::max(map({$self->_length($_);} @{$$n{"subs"};})); } elsif ($k eq "repeat") { my $body = $self->_length($n->{"subs"}[0]); $n->{"max"} == 0 || $body == 0 ? 0 : ($n->{"max"} == -1 ? "Inf" : $n->{"max"} * $body); } else { &List::Util::sum(0, map({$self->_length($_);} @{$$n{"subs"};})); } }
ABresult
1X1
011
000
244 13 my $k = $n->{kind};
245 13 ▶ if ($k eq 'char' || $k eq 'set') { 1 }
Branch: 4 branches
BranchTrueFalseTotal
if ($k eq 'char' or $k eq 'set') { } 4 9 13
elsif ($k eq 'look' or $k eq 'backref' or $k eq 'empty' or _zero_width($k)) { } 4 5 9
elsif ($k eq 'alt') { } 0 5 5
elsif ($k eq 'repeat') { } 3 2 5
Condition100%3/3
$k eq "char" or $k eq "set"
l!l&&r!l&&!r
139
MC/DC100%2/2
$k eq "char" or $k eq "set"
$k eq "char" $k eq "set"
Truth table100%3/3
A or B
A= $k eq "char"B= $k eq "set"
ABresult
1X1
011
000
246 4 ▶ elsif ($k eq 'look' || $k eq 'backref' || $k eq 'empty' || _zero_width($k)) { 0 }
Condition44%4/9
$k eq "look" or $k eq "backref" or $k eq "empty" or _zero_width($k)
l!l&&r!l&&!r
045
$k eq "look" or $k eq "backref" or $k eq "empty"
l!l&&r!l&&!r
009
$k eq "look" or $k eq "backref"
l!l&&r!l&&!r
009
MC/DC25%1/4
$k eq "look" or $k eq "backref" or $k eq "empty" or _zero_width($k)
$k eq "look" $k eq "backref" $k eq "empty" _zero_width($k)
Truth table40%2/5
A or B or C or D
A= $k eq "look"B= $k eq "backref"C= $k eq "empty"D= _zero_width($k)
ABCDresult
1XXX1
01XX1
001X1
00011
00000
247 0 elsif ($k eq 'alt') { List::Util::max(map { $self->_length($_) } @{ $n->{subs} }) }
248 elsif ($k eq 'repeat') {
249 3 my $body = $self->_length($n->{subs}[0]);
250 3 ▶ $n->{max} == 0 || $body == 0 ? 0 : $n->{max} == -1 ? INFINITE : $n->{max} * $body;
Branch: 2 branches
BranchTrueFalseTotal
$n->{'max'} == 0 || $body == 0 ? : 0 3 3
$n->{'max'} == -1 ? : 2 1 3
Condition33%1/3
$n->{"max"} == 0 or $body == 0
l!l&&r!l&&!r
003
MC/DC0%0/2
$n->{"max"} == 0 or $body == 0
$n->{"max"} == 0 $body == 0
Truth table33%1/3
A or B
A= $n->{"max"} == 0B= $body == 0
ABresult
1X1
011
000
251 }
252 2 else { List::Util::sum(0, map { $self->_length($_) } @{ $n->{subs} }) }
253 };
254 }
255  
256 # Whether every way through the node starts with ^, so that a search is tried at the start of the text and nowhere
257 # else.
258 4 ▶sub _anchored {
Subroutine _anchored: called CC=13 SCAR=43.2
259 4 my ($self, $n) = @_;
260 4 my $k = $n->{kind};
261 4 ▶ return 1 if $k eq 'bol';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "bol" 2 2 4
262 2 ▶ if ($k eq 'cat') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "cat") 2 0 2
263 2 for my $x (@{ $n->{subs} }) {
264 2 ▶ return 1 if $self->_anchored($x);
Branch: 1 branch
BranchTrueFalseTotal
if $self->_anchored($x) 2 0 2
265 # Before the ^ there may be what takes no character, other than a lookahead, which would be tried everywhere.
266 0 ▶ return 0 if $self->_length($x) != 0 || _has_look($x);
Branch: 1 branch
BranchTrueFalseTotal
if $self->_length($x) != 0 or _has_look($x) 0 0 0
Condition0%0/3
$self->_length($x) != 0 or _has_look($x)
l!l&&r!l&&!r
000
MC/DC0%0/2
$self->_length($x) != 0 or _has_look($x)
$self->_length($x) != 0 _has_look($x)
Truth table0%0/3
A or B
A= $self->_length($x) != 0B= _has_look($x)
ABresult
1X1
011
000
267 }
268 0 return 0;
269 }
270 0 ▶ return (List::Util::all { $self->_anchored($_) } @{ $n->{subs} }) ? 1 : 0 if $k eq 'alt';
Subroutine __ANON__: not called CC=1 SCAR=6.9
Branch: 2 branches
BranchTrueFalseTotal
if $k eq "alt" 0 0 0
&List::Util::all(sub { $self->_anchored($_); } , @{$$n{'subs'};}) ? : 0 0 0
271 0 ▶ return $self->_anchored($n->{subs}[0]) if $k eq 'group';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "group" 0 0 0
272 0 ▶ return $n->{min} >= 1 && $self->_anchored($n->{subs}[0]) ? 1 : 0 if $k eq 'repeat';
Branch: 2 branches
BranchTrueFalseTotal
if $k eq "repeat" 0 0 0
$n->{'min'} >= 1 && $self->_anchored($n->{'subs'}[0]) ? : 0 0 0
Condition0%0/3
$n->{"min"} >= 1 and $self->_anchored($n->{"subs"}[0])
!ll&&!rl&&r
000
MC/DC0%0/2
$n->{"min"} >= 1 and $self->_anchored($n->{"subs"}[0])
$n->{"min"} >= 1 $self->_anchored($n->{"subs"}[0])
Truth table0%0/3
A and B
A= $n->{"min"} >= 1B= $self->_anchored($n->{"subs"}[0])
ABresult
0X0
100
111
273 0 return 0;
274 }
275  
276 # Marks the lookaheads at the start of an anchored pattern, before anything that takes a character or is a choice.
277 # Each is tried once.
278 2 ▶sub _mark_once {
Subroutine _mark_once: called CC=7 SCAR=20.7
279 2 my ($self, $n) = @_;
280 2 ▶ $n = $n->{subs}[0] while $n->{kind} eq 'group';
Branch: 1 branch
BranchTrueFalseTotal
$n->{"kind"} eq "group" and do { $n = $n->{"subs"}[0] } 0 2 2
281 2 ▶ return unless $n->{kind} eq 'cat';
Branch: 1 branch
BranchTrueFalseTotal
unless $n->{"kind"} eq "cat" 0 2 2
282 2 for my $x (@{ $n->{subs} }) {
283 4 ▶ if ($x->{kind} eq 'look') {
Branch: 2 branches
BranchTrueFalseTotal
if ($x->{'kind'} eq 'look') { } 0 4 4
elsif (not _zero_width($x->{'kind'}) || $x->{'kind'} eq 'empty') { } 2 2 4
284 0 $self->{once}{ Scalar::Util::refaddr($x) } = 1;
285 }
286 ▶ elsif (!(_zero_width($x->{kind}) || $x->{kind} eq 'empty')) {
Condition66%2/3
_zero_width($x->{'kind'}) || $x->{'kind'} eq 'empty'
l!l&&r!l&&!r
202
MC/DC50%1/2
_zero_width($x->{'kind'}) || $x->{'kind'} eq 'empty'
_zero_width($x->{'kind'}) $x->{'kind'} eq 'empty'
Truth table66%2/3
A || B
A= _zero_width($x->{'kind'})B= $x->{'kind'} eq 'empty'
ABresult
1X1
011
000
287 2 return;
288 }
289 }
290 }
291  
292 2 ▶sub _never_fails {
Subroutine _never_fails: called CC=13 SCAR=44.3
293 2 my ($self, $n) = @_;
294 2 my $k = $n->{kind};
295 2 ▶ return 1 if $k eq 'empty';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "empty" 0 2 2
296 2 ▶ return 0 if $k eq 'char' || $k eq 'set' || $k eq 'look' || $k eq 'backref' || _zero_width($k);
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "char" or $k eq "set" or $k eq "look" or $k eq "backref" or _zero_width($k) 2 0 2
Condition33%4/12
$k eq "char" or $k eq "set" or $k eq "look" or $k eq "backref" or _zero_width($k)
l!l&&r!l&&!r
020
$k eq "char" or $k eq "set" or $k eq "look" or $k eq "backref"
l!l&&r!l&&!r
002
$k eq "char" or $k eq "set" or $k eq "look"
l!l&&r!l&&!r
002
$k eq "char" or $k eq "set"
l!l&&r!l&&!r
002
MC/DC0%0/5
$k eq "char" or $k eq "set" or $k eq "look" or $k eq "backref" or _zero_width($k)
$k eq "char" $k eq "set" $k eq "look" $k eq "backref" _zero_width($k)
Truth table16%1/6
A or B or C or D or E
A= $k eq "char"B= $k eq "set"C= $k eq "look"D= $k eq "backref"E= _zero_width($k)
ABCDEresult
1XXXX1
01XXX1
001XX1
0001X1
000011
000000
297 0 ▶ return $n->{min} == 0 || $n->{max} == 0 ? 1 : 0 if $k eq 'repeat';
Branch: 2 branches
BranchTrueFalseTotal
if $k eq "repeat" 0 0 0
$n->{'min'} == 0 || $n->{'max'} == 0 ? : 0 0 0
Condition0%0/3
$n->{"min"} == 0 or $n->{"max"} == 0
l!l&&r!l&&!r
000
MC/DC0%0/2
$n->{"min"} == 0 or $n->{"max"} == 0
$n->{"min"} == 0 $n->{"max"} == 0
Truth table0%0/3
A or B
A= $n->{"min"} == 0B= $n->{"max"} == 0
ABresult
1X1
011
000
298 0 ▶ return (List::Util::any { $self->_never_fails($_) } @{ $n->{subs} }) ? 1 : 0 if $k eq 'alt';
Subroutine __ANON__: not called CC=1 SCAR=6.9
Branch: 2 branches
BranchTrueFalseTotal
if $k eq "alt" 0 0 0
&List::Util::any(sub { $self->_never_fails($_); } , @{$$n{'subs'};}) ? : 0 0 0
299 0 ▶ return (List::Util::all { $self->_never_fails($_) } @{ $n->{subs} }) ? 1 : 0;
Subroutine __ANON__: not called CC=1 SCAR=6.9
Branch: 1 branch
BranchTrueFalseTotal
&List::Util::all(sub { $self->_never_fails($_); } , @{$$n{'subs'};}) ? : 0 0 0
300 }
301  
302 # The most characters a try at the node can take and still fail. $last: once the node has matched, nothing after it
303 # can fail.
304 2 ▶sub _fails_within {
Subroutine _fails_within: called CC=19 SCAR=53.8
305 2 my ($self, $n, $last) = @_;
306 2 my $k = $n->{kind};
307 2 ▶ return $k ne 'look' ? $self->_length($n) : $self->_length($n->{subs}[0]) unless $last;
Branch: 2 branches
BranchTrueFalseTotal
unless $last 0 2 2
$k ne 'look' ? : 0 0 0
308 2 ▶ return 1 if $k eq 'char' || $k eq 'set';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "char" or $k eq "set" 0 2 2
Condition33%1/3
$k eq "char" or $k eq "set"
l!l&&r!l&&!r
002
MC/DC0%0/2
$k eq "char" or $k eq "set"
$k eq "char" $k eq "set"
Truth table33%1/3
A or B
A= $k eq "char"B= $k eq "set"
ABresult
1X1
011
000
309 2 ▶ return 0 if $k eq 'empty' || $k eq 'backref' || _zero_width($k);
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "empty" or $k eq "backref" or _zero_width($k) 2 0 2
Condition33%2/6
$k eq "empty" or $k eq "backref" or _zero_width($k)
l!l&&r!l&&!r
020
$k eq "empty" or $k eq "backref"
l!l&&r!l&&!r
002
MC/DC0%0/3
$k eq "empty" or $k eq "backref" or _zero_width($k)
$k eq "empty" $k eq "backref" _zero_width($k)
Truth table25%1/4
A or B or C
A= $k eq "empty"B= $k eq "backref"C= _zero_width($k)
ABCresult
1XX1
01X1
0011
0000
310 0 ▶ return $self->_length($n->{subs}[0]) if $k eq 'look';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "look" 0 0 0
311 0 ▶ return $self->_fails_within($n->{subs}[0], 1) if $k eq 'group';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "group" 0 0 0
312 0 ▶ return List::Util::max(map { $self->_fails_within($_, 1) } @{ $n->{subs} }) if $k eq 'alt';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "alt" 0 0 0
313 0 ▶ if ($k eq 'repeat') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "repeat") 0 0 0
314 0 ▶ return 0 if $n->{max} == 0 || $n->{min} == 0;
Branch: 1 branch
BranchTrueFalseTotal
if $n->{"max"} == 0 or $n->{"min"} == 0 0 0 0
Condition0%0/3
$n->{"max"} == 0 or $n->{"min"} == 0
l!l&&r!l&&!r
000
MC/DC0%0/2
$n->{"max"} == 0 or $n->{"min"} == 0
$n->{"max"} == 0 $n->{"min"} == 0
Truth table0%0/3
A or B
A= $n->{"max"} == 0B= $n->{"min"} == 0
ABresult
1X1
011
000
315 0 my $body = $n->{subs}[0];
316 0 ▶ my $before = $n->{min} > 1 ? ($n->{min} - 1) * $self->_length($body) : 0;
Branch: 1 branch
BranchTrueFalseTotal
$n->{'min'} > 1 ? : 0 0 0
317 0 return $before + $self->_fails_within($body, 1);
318 }
319 # A sequence: the items after the last one that can fail cost nothing.
320 0 my $items = $n->{subs};
321 0 my $j = $#$items;
322 0 ▶ $j-- while $j >= 0 && $self->_never_fails($items->[$j]);
Branch: 1 branch
BranchTrueFalseTotal
$j >= 0 and $self->_never_fails($items->[$j]) and do { --$j } 0 0 0
Condition0%0/3
$j >= 0 and $self->_never_fails($items->[$j])
!ll&&!rl&&r
000
MC/DC0%0/2
$j >= 0 and $self->_never_fails($items->[$j])
$j >= 0 $self->_never_fails($items->[$j])
Truth table0%0/3
A and B
A= $j >= 0B= $self->_never_fails($items->[$j])
ABresult
0X0
100
111
323 0 ▶ return 0 if $j < 0;
Branch: 1 branch
BranchTrueFalseTotal
if $j < 0 0 0 0
324 0 my $width = $self->_fails_within($items->[$j], 1);
325 0 $width += $self->_fails_within($items->[$_], 0) for 0 .. $j - 1;
326 0 return $width;
327 }
328  
329 # Checks the node. $follow: the characters that can come after it. $end: the pattern (or the lookahead the node is in)
330 # can end after it. $after: the most characters that what comes after it can take and still fail, and $never: what
331 # comes after it cannot fail. $single: the node is in no repetition.
332 13 ▶sub _visit {
Subroutine _visit: called CC=51 SCAR=62.1
333 13 my ($self, $n, $follow, $end, $after, $never, $single) = @_;
334 13 $self->{nodes}++;
335 13 ▶ $self->{repeated}++ unless $single;
Branch: 1 branch
BranchTrueFalseTotal
unless $single 2 11 13
336 13 my $k = $n->{kind};
337 return if $k eq 'char' || $k eq 'set' || $k eq 'empty' || $k eq 'bol' || $k eq 'eol' || $k eq 'line_start'
338 13 ▶ || $k eq 'line_end' || (($k eq 'wb' || $k eq 'nwb') && !$n->{fold});
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "char" or $k eq "set" or $k eq "empty" or $k eq "bol" or $k eq "eol" or $k eq "line_start" or $k eq "line_end" or $k eq "wb" || $k eq "nwb" and not $n->{"fold"} 8 5 13
Condition70%19/27
$k eq "char" or $k eq "set" or $k eq "empty" or $k eq "bol" or $k eq "eol" or $k eq "line_start" or $k eq "line_end" or $k eq "wb" || $k eq "nwb" and not $n->{"fold"}
l!l&&r!l&&!r
805
$k eq "char" or $k eq "set" or $k eq "empty" or $k eq "bol" or $k eq "eol" or $k eq "line_start" or $k eq "line_end"
l!l&&r!l&&!r
805
$k eq "char" or $k eq "set" or $k eq "empty" or $k eq "bol" or $k eq "eol" or $k eq "line_start"
l!l&&r!l&&!r
805
$k eq "char" or $k eq "set" or $k eq "empty" or $k eq "bol" or $k eq "eol"
l!l&&r!l&&!r
625
$k eq "char" or $k eq "set" or $k eq "empty" or $k eq "bol"
l!l&&r!l&&!r
427
$k eq "char" or $k eq "set" or $k eq "empty"
l!l&&r!l&&!r
409
$k eq "char" or $k eq "set"
l!l&&r!l&&!r
139
$k eq "wb" || $k eq "nwb" and not $n->{"fold"}
!ll&&!rl&&r
500
$k eq "wb" or $k eq "nwb"
l!l&&r!l&&!r
005
MC/DC40%4/10
$k eq "char" or $k eq "set" or $k eq "empty" or $k eq "bol" or $k eq "eol" or $k eq "line_start" or $k eq "line_end" or $k eq "wb" || $k eq "nwb" and not $n->{"fold"}
$k eq "char" $k eq "set" $k eq "empty" $k eq "bol" $k eq "eol" $k eq "line_start" $k eq "line_end" $k eq "wb" $k eq "nwb" not $n->{"fold"}
Truth table41%5/12
A or B or C or D or E or F or G or H or I and not(J)
A= $k eq "char"B= $k eq "set"C= $k eq "empty"D= $k eq "bol"E= $k eq "eol"F= $k eq "line_start"G= $k eq "line_end"H= $k eq "wb"I= $k eq "nwb"J= not $n->{"fold"}
ABCDEFGHIJresult
1XXXXXXXXX1
01XXXXXXXX1
001XXXXXXX1
0001XXXXXX1
00001XXXXX1
000001XXXX1
0000001XXX1
00000001X11
00000000111
000000000X0
00000001X00
00000000100
339 5 ▶ _not_linear() if $k eq 'backref' || $k eq 'wb' || $k eq 'nwb';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "backref" or $k eq "wb" or $k eq "nwb" 0 5 5
Condition33%2/6
$k eq "backref" or $k eq "wb" or $k eq "nwb"
l!l&&r!l&&!r
005
$k eq "backref" or $k eq "wb"
l!l&&r!l&&!r
005
MC/DC0%0/3
$k eq "backref" or $k eq "wb" or $k eq "nwb"
$k eq "backref" $k eq "wb" $k eq "nwb"
Truth table25%1/4
A or B or C
A= $k eq "backref"B= $k eq "wb"C= $k eq "nwb"
ABCresult
1XX1
01X1
0011
0000
340 5 ▶ if ($k eq 'group') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "group") 0 5 5
341 0 $self->_visit($n->{subs}[0], $follow, $end, $after, $never, $single);
342 0 return;
343 }
344 5 ▶ if ($k eq 'look') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "look") 0 5 5
345 0 ▶ _not_linear() if $n->{behind};
Branch: 1 branch
BranchTrueFalseTotal
if $n->{"behind"} 0 0 0
346 0 my $width = $self->_length($n->{subs}[0]);
347 0 ▶ if ($width == INFINITE) {
Branch: 1 branch
BranchTrueFalseTotal
if ($width == 9**9**9) { } 0 0 0
348 0 ▶ _not_linear() unless $self->{once}{ Scalar::Util::refaddr($n) };
Branch: 1 branch
BranchTrueFalseTotal
unless $self->{"once"}{builtin::refaddr($n)} 0 0 0
349 }
350 else {
351 0 $self->_cost($width);
352 }
353 0 $self->_visit($n->{subs}[0], [], 1, 0, 1, $single);
354 0 return;
355 }
356 5 ▶ if ($k eq 'cat') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "cat") 2 3 5
357 2 my $items = $n->{subs};
358 2 ▶ for (my $i = $#$items; $i >= 0; $i--) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i >= 0) 8 2 10
359 8 my $x = $items->[$i];
360 8 $self->_visit($x, $follow, $end, $after, $never, $single);
361 8 ▶ if (matches_nothing($x)) {
Branch: 1 branch
BranchTrueFalseTotal
if (matches_nothing($x)) { } 7 1 8
362 7 $follow = _merged([ @$follow, @{ $self->_first($x) } ]);
363 }
364 else {
365 1 ($follow, $end) = ($self->_first($x), 0);
366 }
367 8 ▶ if ($never) {
Branch: 1 branch
BranchTrueFalseTotal
if ($never) { } 2 6 8
368 2 ▶ ($after, $never) = ($self->_fails_within($x, 1), 0) unless $self->_never_fails($x);
Branch: 1 branch
BranchTrueFalseTotal
unless $self->_never_fails($x) 2 0 2
369 }
370 else {
371 6 $after += $self->_length($x);
372 }
373 }
374 2 return;
375 }
376 3 ▶ if ($k eq 'alt') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "alt") 0 3 3
377 0 my $seen = [];
378 0 my ($nothing, $clash) = (0, 0);
379 0 for my $x (@{ $n->{subs} }) {
380 0 my $starts = $self->_first($x);
381 0 ▶ if (matches_nothing($x)) {
Branch: 1 branch
BranchTrueFalseTotal
if (matches_nothing($x)) 0 0 0
382 0 ▶ $clash ||= $nothing;
Condition0%0/3
$clash ||= $nothing
l!l&&r!l&&!r
000
MC/DC0%0/2
$clash ||= $nothing
$clash $nothing
Truth table0%0/3
A ||= B
A= $clashB= $nothing
ABresult
1X1
011
000
383 0 $nothing = 1;
384 0 $starts = _merged([ @$starts, @$follow ]);
385 }
386 0 ▶ $clash ||= _meet($seen, $starts);
Condition0%0/3
$clash ||= _meet($seen, $starts)
l!l&&r!l&&!r
000
MC/DC0%0/2
$clash ||= _meet($seen, $starts)
$clash _meet($seen, $starts)
Truth table0%0/3
A ||= B
A= $clashB= _meet($seen, $starts)
ABresult
1X1
011
000
387 0 $seen = _merged([ @$seen, @$starts ]);
388 }
389 0 ▶ if ($clash) {
Branch: 1 branch
BranchTrueFalseTotal
if ($clash) 0 0 0
390 # The next character does not say which alternative to take.
391 0 ▶ my $ways = $self->_length($n) <= MAX_WORK ? $self->_ways($n) : undef;
Branch: 1 branch
BranchTrueFalseTotal
$self->_length($n) <= 4096 ? : 0 0 0
392 0 ▶ _not_linear() unless $ways;
Branch: 1 branch
BranchTrueFalseTotal
unless $ways 0 0 0
393 0 my $overlap = 0;
394 0 OUTER: for my $i (0 .. $#$ways) {
395 0 for my $j (0 .. $i - 1) {
396 0 ▶ if (_starts_with($ways->[$i], $ways->[$j])) {
Branch: 1 branch
BranchTrueFalseTotal
if (_starts_with($ways->[$i], $ways->[$j])) 0 0 0
397 0 $overlap = 1;
398 0 last OUTER;
399 }
400 }
401 }
402 0 ▶ if ($overlap) {
Branch: 1 branch
BranchTrueFalseTotal
if ($overlap) 0 0 0
403 # A text can match two of them. Each is a way to go on.
404 0 ▶ _not_linear() unless $single;
Branch: 1 branch
BranchTrueFalseTotal
unless $single 0 0 0
405 0 $self->_cost(@$ways - 1);
406 }
407 0 my $count = List::Util::sum(0, map { scalar @$_ } @$ways);
408 0 $self->{nodes} += $count;
409 0 ▶ $self->{repeated} += $count unless $single;
Branch: 1 branch
BranchTrueFalseTotal
unless $single 0 0 0
410 }
411 0 $self->_visit($_, $follow, $end, $after, $never, $single) for @{ $n->{subs} };
412 0 return;
413 }
414 # A repetition.
415 3 ▶ return if $n->{max} == 0;
Branch: 1 branch
BranchTrueFalseTotal
if $n->{"max"} == 0 0 3 3
416 3 my $body = $n->{subs}[0];
417 3 ▶ if (only_nothing($body)) {
Branch: 1 branch
BranchTrueFalseTotal
if (only_nothing($body)) 0 3 3
418 # Written as the body once, or as nothing.
419 0 ▶ $self->_visit($body, $follow, $end, $after, $never, $single) if $n->{min};
Branch: 1 branch
BranchTrueFalseTotal
if $n->{"min"} 0 0 0
420 0 return;
421 }
422 3 ▶ if ($n->{max} == 1 && $n->{min} == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n->{"max"} == 1 and $n->{"min"} == 1) 0 3 3
Condition66%2/3
$n->{"max"} == 1 and $n->{"min"} == 1
!ll&&!rl&&r
210
MC/DC0%0/2
$n->{"max"} == 1 and $n->{"min"} == 1
$n->{"max"} == 1 $n->{"min"} == 1
Truth table66%2/3
A and B
A= $n->{"max"} == 1B= $n->{"min"} == 1
ABresult
0X0
100
111
423 0 $self->_visit($body, $follow, $end, $after, $never, $single);
424 0 return;
425 }
426 3 ▶ _not_linear() if matches_nothing($body);
Branch: 1 branch
BranchTrueFalseTotal
if matches_nothing($body) 0 3 3
427 3 my $starts = $self->_first($body);
428 3 ▶ if ($n->{min} != $n->{max} && _meet($starts, $follow)) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n->{"min"} != $n->{"max"} and _meet($starts, $follow)) 0 3 3
Condition33%1/3
$n->{"min"} != $n->{"max"} and _meet($starts, $follow)
!ll&&!rl&&r
030
MC/DC0%0/2
$n->{"min"} != $n->{"max"} and _meet($starts, $follow)
$n->{"min"} != $n->{"max"} _meet($starts, $follow)
Truth table33%1/3
A and B
A= $n->{"min"} != $n->{"max"}B= _meet($starts, $follow)
ABresult
0X0
100
111
429 # The next character does not say whether to leave the repetition. Each place to leave it is tried.
430 0 ▶ _not_linear() if $after == INFINITE;
Branch: 1 branch
BranchTrueFalseTotal
if $after == "Inf" 0 0 0
431 0 $self->_cost($after);
432 }
433 3 ▶ if ($n->{max} == 1) {
Branch: 1 branch
BranchTrueFalseTotal
if ($n->{'max'} == 1) { } 1 2 3
434 1 $self->_visit($body, $follow, $end, $after, $never, $single);
435 }
436 else {
437 2 ▶ my $rest = $n->{max} == -1 ? INFINITE : $after + ($n->{max} - 1) * $self->_length($body);
Branch: 1 branch
BranchTrueFalseTotal
$n->{'max'} == -1 ? : 2 0 2
438 2 $self->_visit($body, _merged([ @$follow, @$starts ]), $end, $rest, 0, 0);
439 }
440 }
441  
442 4 1;
« Corvus/Collecting.pm ↑ Summary Corvus/CodeGen.pm »