Corvus/Pattern.pm

filter: Statementstmt 82.5% 109 / 132 Branchbran 53.9% 55 / 102 Conditioncond 56.4% 22 / 39 MC/DCmcdc 34.7% 8 / 23 Subroutinesub 86.9% 20 / 23 Podpod 0.0% 0 / 2 totaltotal 66.6% 214 / 321 CC 70 SCAR 40.1
CC
70
Cov
68%
_perl_regex
122.0
_perl_set
13.9
__ANON__
12.0
CRAP 55.2
« Corvus/Dialect.pm ↑ Summary Corvus/Json.pm »
1 package JSON::Schema::Corvus::Pattern;
2  
3 # ECMA-262 regular expressions, as JSON Schema's pattern and format: regex specify, run with ECMA-262's meaning.
4 #
5 # A pattern is read with the grammar of the u flag, and one that only that grammar refuses is read with the Annex B
6 # grammar of a pattern with no flag, as the other ports do (Regex::Parse). Two engines run what is read:
7 #
8 # - Perl's own engine runs a pattern that Regex::Linear proves it matches in time proportional to the text, written
9 # out with ECMA-262's meaning: every literal and class as code points (so Perl's own \d, \w, \s, the dot and its
10 # Unicode tables never apply), ^ and $ as the ends of the text, \b with ECMA-262's ASCII word characters. Such a
11 # match needs no limit, and Perl's engine has none: it cannot be stopped once it has started.
12 # - The matcher of Regex::Vm runs every other pattern (a backreference, a lookbehind, a case-insensitive word
13 # boundary, a count Perl cannot write, or anything the proof does not prove), with the limit of a match.
14 #
15 # A pattern read without the u flag is matched by UTF-16 code unit, so on a text with a character beyond the Basic
16 # Multilingual Plane it always goes to the matcher, which reads the text that way.
17  
18 4 ▶use 5.026;
Subroutine BEGIN: called CC=1 SCAR=0.0
19 4 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
20 4 ▶use warnings;
Subroutine BEGIN: called CC=1 SCAR=0.0
21 4 ▶use JSON::Schema::Corvus::Error;
Subroutine BEGIN: called CC=1 SCAR=0.0
22 4 ▶use JSON::Schema::Corvus::Regex::Charset ();
Subroutine BEGIN: called CC=1 SCAR=0.0
23 4 ▶use JSON::Schema::Corvus::Regex::Linear ();
Subroutine BEGIN: called CC=1 SCAR=0.0
24 4 ▶use JSON::Schema::Corvus::Regex::Parse ();
Subroutine BEGIN: called CC=1 SCAR=0.0
25 4 ▶use JSON::Schema::Corvus::Regex::Vm ();
Subroutine BEGIN: called CC=1 SCAR=0.0
26  
27 4 ▶use constant DEFAULT_MATCH_LIMIT => 1.0;
Subroutine BEGIN: called CC=1 SCAR=0.0
28 # The largest count of a quantifier Perl's engine reads.
29 4 ▶use constant MAX_PERL_COUNT => 32766;
Subroutine BEGIN: called CC=1 SCAR=0.0
30 # The most compiled patterns kept, by pattern and limit.
31 4 ▶use constant MAX_CACHED => 512;
Subroutine BEGIN: called CC=1 SCAR=0.0
32  
33 4 my %CACHE;
34  
35 # Reads a pattern: (tree, unicode) in the u flag grammar or else Annex B, or () for a pattern neither accepts. Dies with
36 # a PatternTooLarge error for a pattern over a limit of size.
37 6 ▶sub _read {
Subroutine _read: called CC=5 SCAR=16.1
38 6 my ($pattern) = @_;
39 6 for my $unicode (1, 0) {
40 7 my ($root) = eval { JSON::Schema::Corvus::Regex::Parse::parse($pattern, $unicode) };
41 7 ▶ return ($root, $unicode) if $root;
Branch: 1 branch
BranchTrueFalseTotal
if $root 4 3 7
42 3 my $e = $@;
43 3 ▶ die $e unless ref $e eq 'HASH';
Branch: 1 branch
BranchTrueFalseTotal
unless ref $e eq "HASH" 0 3 3
44 3 ▶ _too_large($pattern, $e) if $e->{too_large};
Branch: 1 branch
BranchTrueFalseTotal
if $e->{"too_large"} 1 2 3
45 }
46 1 return ();
47 }
48  
49 2 ▶sub _shown {
Subroutine _shown: called CC=2 SCAR=6.9
50 2 my ($pattern) = @_;
51 2 ▶ return length $pattern <= 200 ? $pattern : substr($pattern, 0, 200) . '... (' . length($pattern) . ' characters)';
Branch: 1 branch
BranchTrueFalseTotal
length $pattern <= 200 ? : 1 1 2
52 }
53  
54 1 ▶sub _too_large {
Subroutine _too_large: called CC=3 SCAR=13.1
55 1 my ($pattern, $e) = @_;
56 my $why = $e->{too_large} eq 'length' ? "the pattern is longer than $e->{value} bytes"
57 1 ▶ : $e->{too_large} eq 'nesting' ? "the groups of the pattern nest more than $e->{value} deep"
Branch: 2 branches
BranchTrueFalseTotal
$e->{'too_large'} eq 'length' ? : 1 0 1
$e->{'too_large'} eq 'nesting' ? : 0 0 0
58 : "the pattern has a size of more than $e->{value} bytes when it is read";
59 1 die JSON::Schema::Corvus::Error::PatternTooLarge->_new(
60 "The regular expression '" . _shown($pattern) . "' is over a limit of size: $why.", pattern => $pattern);
61 }
62  
63 # Whether the text is a valid regular expression for format: regex, which takes the u flag grammar only, as the other
64 # ports do. A text over a limit of reading is not valid.
65 0 ▶sub is_valid_ecma_regex {
Subroutine is_valid_ecma_regex: not called CC=2 SCAR=17.9
Pod undocumented
66 0 my ($s) = @_;
67 0 ▶ return eval { JSON::Schema::Corvus::Regex::Parse::parse($s, 1); 1 } ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
eval { do { JSON::Schema::Corvus::Regex::Parse::parse($s, 1); 1 } } ? : 0 0 0
68 }
69  
70 # The search function of a pattern (true on a match), or undef for a pattern that is not valid. $limit is the seconds
71 # one match may take (undef: no limit); a match that reaches it dies with a PatternMatchLimit error. Dies with a
72 # PatternTooLarge error for a pattern over a limit of size.
73 89 ▶sub compile_pattern {
Subroutine compile_pattern: called CC=4 SCAR=13.9
Pod undocumented
74 89 my ($pattern, $limit) = @_;
75 89 ▶ my $key = ($limit // 'none') . "\0" . $pattern;
Condition100%2/2
$limit // "none"
l!l
836
MC/DC100%1/1
$limit // "none"
$limit
Truth table100%2/2
A
A= $limit
Aresult
11
00
76 89 ▶ return $CACHE{$key} if exists $CACHE{$key};
Branch: 1 branch
BranchTrueFalseTotal
if exists $CACHE{$key} 83 6 89
77 6 ▶ %CACHE = () if keys %CACHE >= MAX_CACHED;
Branch: 1 branch
BranchTrueFalseTotal
if keys %CACHE >= 512 0 6 6
78 6 return $CACHE{$key} = _compile($pattern, $limit);
79 }
80  
81 6 ▶sub _compile {
Subroutine _compile: called CC=6 SCAR=20.1
82 6 my ($pattern, $limit) = @_;
83 6 ▶ my ($root, $unicode) = _read($pattern) or return undef;
Branch: 1 branch
BranchTrueFalseTotal
() = _read($pattern) or return undef 4 1 5
84 4 my $tree = JSON::Schema::Corvus::Regex::Vm::_simplify($root, []);
85 4 my $perl = _perl_regex($tree);
86 4 my $vm;
87 4 ▶ my $vm_search = sub {
Subroutine __ANON__: called CC=7 SCAR=20.5
88 4 my ($s) = @_;
89 4 ▶ $vm //= JSON::Schema::Corvus::Regex::Vm::compile_program($root, $unicode);
Condition66%2/3
$vm //= JSON::Schema::Corvus::Regex::Vm::compile_program($root, $unicode)
l!l&&r!l&&!r
220
MC/DC0%0/2
$vm //= JSON::Schema::Corvus::Regex::Vm::compile_program($root, $unicode)
$vm JSON::Schema::Corvus::Regex::Vm::compile_program($root, $unicode)
Truth table66%2/3
A //= B
A= $vmB= JSON::Schema::Corvus::Regex::Vm::compile_program($root, $unicode)
ABresult
1X1
011
000
90 4 my ($ok, $stop) = $vm->match($s, $limit);
91 4 ▶ return $ok if defined $ok;
Branch: 1 branch
BranchTrueFalseTotal
if defined $ok 3 1 4
92 1 ▶ my $time = !defined $limit ? '' : $limit >= 1 ? sprintf('%gs', $limit) : $limit >= 1e-3
Branch: 3 branches
BranchTrueFalseTotal
!defined($limit) ? : 0 1 1
$limit >= 1 ? : 0 1 1
$limit >= 0.001 ? : 1 0 1
93 ? sprintf('%gms', $limit * 1e3) : sprintf("%g\x{b5}s", $limit * 1e6);
94 1 ▶ my $message = $stop eq 'time'
Branch: 1 branch
BranchTrueFalseTotal
$stop eq 'time' ? : 1 0 1
95 ? "A match of the regular expression '" . _shown($pattern) . "' was abandoned: it took longer than the limit of $time."
96 : "A match of the regular expression '" . _shown($pattern)
97 . "' was abandoned: it needed more memory for its backtracking than the limit.";
98 1 die JSON::Schema::Corvus::Error::PatternMatchLimit->_new($message, pattern => $pattern, limit => $limit);
99 4 };
100 # With no limit, Perl's engine runs what it can write, proved or not.
101 4 ▶ return $vm_search unless defined $perl && (!defined $limit || JSON::Schema::Corvus::Regex::Linear->new->proves($tree));
Branch: 1 branch
BranchTrueFalseTotal
unless defined $perl and !defined($limit) || "JSON::Schema::Corvus::Regex::Linear"->new->proves($tree) 2 2 4
Condition50%3/6
defined $perl and !defined($limit) || "JSON::Schema::Corvus::Regex::Linear"->new->proves($tree)
!ll&&!rl&&r
202
not defined $limit or "JSON::Schema::Corvus::Regex::Linear"->new->proves($tree)
l!l&&r!l&&!r
020
MC/DC33%1/3
defined $perl and !defined($limit) || "JSON::Schema::Corvus::Regex::Linear"->new->proves($tree)
defined $perl not defined $limit "JSON::Schema::Corvus::Regex::Linear"->new->proves($tree)
Truth table50%2/4
A and not(B) or C
A= defined $perlB= not defined $limitC= "JSON::Schema::Corvus::Regex::Linear"->new->proves($tree)
ABCresult
0XX0
1000
11X1
1011
102 4 ▶ my $re = do { no warnings; qr/$perl/ };
Subroutine BEGIN: called CC=1 SCAR=0.0
103 0 ▶ return sub { $_[0] =~ $re ? 1 : 0 } if $unicode;
Subroutine __ANON__: not called CC=2 SCAR=11.6
Branch: 2 branches
BranchTrueFalseTotal
if $unicode 2 0 2
$_[0] =~ /$re/u ? : 0 0 0
104 # A pattern read by code unit: Perl's engine reads code points, which differ only for a text with a character beyond
105 # the Basic Multilingual Plane.
106 0 ▶ return sub {
Subroutine __ANON__: not called CC=3 SCAR=24.8
107 0 ▶ return $vm_search->($_[0]) if $_[0] =~ /[\x{10000}-\x{10FFFF}]/;
Branch: 1 branch
BranchTrueFalseTotal
if $_[0] =~ /[\x{10000}-\x{10FFFF}]/u 0 0 0
108 0 ▶ return $_[0] =~ $re ? 1 : 0;
Branch: 1 branch
BranchTrueFalseTotal
$_[0] =~ /$re/u ? : 0 0 0
109 0 };
110 }
111  
112 # A class for Perl's engine. A class of at most four characters is written as an alternation of them: Perl compiles a
113 # class whose members are one case folding set (such as [\x{1f80}\x{1f88}]) to a node that compares with full case
114 # folding, which answers wrongly for a character whose full folding is more than one character (5.40 matches neither of
115 # those two with it). A case folding set has at most four members.
116 3 ▶sub _perl_set {
Subroutine _perl_set: called CC=7 SCAR=26.3
117 3 my ($set) = @_;
118 3 my $r = $set->{ranges};
119 3 my $count = 0;
120 3 ▶ for (my $i = 0; $i < @$r; $i += 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < @$r) 4 0 4
121 4 $count += $r->[$i + 1] - $r->[$i] + 1;
122 4 ▶ last if $count > 4;
Branch: 1 branch
BranchTrueFalseTotal
if $count > 4 3 1 4
123 }
124 3 ▶ return $set->class_text if $count > 4 || $count == 0;
Branch: 1 branch
BranchTrueFalseTotal
if $count > 4 or $count == 0 3 0 3
Condition33%1/3
$count > 4 or $count == 0
l!l&&r!l&&!r
300
MC/DC0%0/2
$count > 4 or $count == 0
$count > 4 $count == 0
Truth table33%1/3
A or B
A= $count > 4B= $count == 0
ABresult
1X1
011
000
125 0 my @members;
126 0 ▶ for (my $i = 0; $i < @$r; $i += 2) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i < @$r) 0 0 0
127 0 push @members, map { sprintf('\x{%x}', $_) } $r->[$i] .. $r->[$i + 1];
128 }
129 0 ▶ return @members == 1 ? $members[0] : '(?:' . join('|', @members) . ')';
Branch: 1 branch
BranchTrueFalseTotal
@members == 1 ? : 0 0 0
130 }
131  
132 # The pattern written for Perl's engine, or undef when it has what that engine cannot run with ECMA-262's meaning: a
133 # backreference, a lookbehind, a case-insensitive word boundary, or a count Perl cannot write.
134 33 ▶sub _perl_regex {
Subroutine _perl_regex: called CC=39 SCAR=48.0
135 33 my ($n) = @_;
136 33 my $k = $n->{kind};
137 33 ▶ return '(?:)' if $k eq 'empty';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "empty" 0 33 33
138 33 ▶ return sprintf('\x{%x}', $n->{r}) if $k eq 'char';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "char" 3 30 33
139 30 ▶ return _perl_set($n->{set}) if $k eq 'set';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "set" 3 27 30
140 27 ▶ if ($k eq 'cat') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "cat") 6 21 27
141 6 my $out = '';
142 6 for (@{ $n->{subs} }) {
143 16 ▶ my $part = _perl_regex($_) // return undef;
Condition100%2/2
_perl_regex($_) // (return undef)
l!l
124
MC/DC100%1/1
_perl_regex($_) // (return undef)
_perl_regex($_)
Truth table100%2/2
A
A= _perl_regex($_)
Aresult
11
00
144 12 ▶ $out .= $_->{kind} eq 'alt' ? "(?:$part)" : $part;
Branch: 1 branch
BranchTrueFalseTotal
$_->{'kind'} eq 'alt' ? : 0 12 12
145 }
146 2 return $out;
147 }
148 21 ▶ if ($k eq 'alt') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "alt") 0 21 21
149 0 my @parts;
150 0 for (@{ $n->{subs} }) {
151 0 ▶ push @parts, _perl_regex($_) // return undef;
Condition0%0/2
_perl_regex($_) // (return undef)
l!l
00
MC/DC0%0/1
_perl_regex($_) // (return undef)
_perl_regex($_)
Truth table0%0/2
A
A= _perl_regex($_)
Aresult
11
00
152 }
153 0 return join '|', @parts;
154 }
155 21 ▶ if ($k eq 'group') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "group") 4 17 21
156 4 ▶ my $body = _perl_regex($n->{subs}[0]) // return undef;
Condition100%2/2
_perl_regex($n->{"subs"}[0]) // (return undef)
l!l
22
MC/DC100%1/1
_perl_regex($n->{"subs"}[0]) // (return undef)
_perl_regex($n->{"subs"}[0])
Truth table100%2/2
A
A= _perl_regex($n->{"subs"}[0])
Aresult
11
00
157 2 return "(?:$body)";
158 }
159 17 ▶ if ($k eq 'repeat') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "repeat") 9 8 17
160 9 ▶ return '(?:)' if $n->{max} == 0;
Branch: 1 branch
BranchTrueFalseTotal
if $n->{"max"} == 0 0 9 9
161 9 ▶ return undef if $n->{min} > MAX_PERL_COUNT || $n->{max} > MAX_PERL_COUNT;
Branch: 1 branch
BranchTrueFalseTotal
if $n->{"min"} > 32766 or $n->{"max"} > 32766 0 9 9
Condition33%1/3
$n->{"min"} > 32766 or $n->{"max"} > 32766
l!l&&r!l&&!r
009
MC/DC0%0/2
$n->{"min"} > 32766 or $n->{"max"} > 32766
$n->{"min"} > 32766 $n->{"max"} > 32766
Truth table33%1/3
A or B
A= $n->{"min"} > 32766B= $n->{"max"} > 32766
ABresult
1X1
011
000
162 9 ▶ my $body = _perl_regex($n->{subs}[0]) // return undef;
Condition100%2/2
_perl_regex($n->{"subs"}[0]) // (return undef)
l!l
54
MC/DC100%1/1
_perl_regex($n->{"subs"}[0]) // (return undef)
_perl_regex($n->{"subs"}[0])
Truth table100%2/2
A
A= _perl_regex($n->{"subs"}[0])
Aresult
11
00
163 my $q = $n->{min} == 0 && $n->{max} == -1 ? '*' : $n->{min} == 1 && $n->{max} == -1 ? '+'
164 : $n->{min} == 0 && $n->{max} == 1 ? '?' : $n->{max} == -1 ? "{$n->{min},}"
165 5 ▶ : $n->{min} == $n->{max} ? "{$n->{min}}" : "{$n->{min},$n->{max}}";
Branch: 5 branches
BranchTrueFalseTotal
$n->{'min'} == 0 && $n->{'max'} == -1 ? : 2 3 5
$n->{'min'} == 1 && $n->{'max'} == -1 ? : 2 1 3
$n->{'min'} == 0 && $n->{'max'} == 1 ? : 1 0 1
$n->{'max'} == -1 ? : 0 0 0
$n->{'min'} == $n->{'max'} ? : 0 0 0
Condition66%6/9
$n->{"min"} == 0 and $n->{"max"} == -1
!ll&&!rl&&r
212
$n->{"min"} == 1 and $n->{"max"} == -1
!ll&&!rl&&r
102
$n->{"min"} == 0 and $n->{"max"} == 1
!ll&&!rl&&r
001
MC/DC100%2/2
$n->{"min"} == 0 and $n->{"max"} == -1
$n->{"min"} == 0 $n->{"max"} == -1
MC/DC50%1/2
$n->{"min"} == 1 and $n->{"max"} == -1
$n->{"min"} == 1 $n->{"max"} == -1
MC/DC0%0/2
$n->{"min"} == 0 and $n->{"max"} == 1
$n->{"min"} == 0 $n->{"max"} == 1
Truth table100%3/3
A and B
A= $n->{"min"} == 0B= $n->{"max"} == -1
ABresult
0X0
100
111
Truth table66%2/3
A and B
A= $n->{"min"} == 1B= $n->{"max"} == -1
ABresult
0X0
100
111
Truth table33%1/3
A and B
A= $n->{"min"} == 0B= $n->{"max"} == 1
ABresult
0X0
100
111
166 5 ▶ return "(?:$body)$q" . ($n->{lazy} ? '?' : '');
Branch: 1 branch
BranchTrueFalseTotal
$n->{'lazy'} ? : 0 5 5
167 }
168 8 ▶ return '\A' if $k eq 'bol';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "bol" 4 4 8
169 4 ▶ return '\z' if $k eq 'eol';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "eol" 2 2 4
170 2 ▶ return '(?<![^\n\r\x{2028}\x{2029}])' if $k eq 'line_start';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "line_start" 0 2 2
171 2 ▶ return '(?![^\n\r\x{2028}\x{2029}])' if $k eq 'line_end';
Branch: 1 branch
BranchTrueFalseTotal
if $k eq "line_end" 0 2 2
172 2 ▶ if ($k eq 'wb' || $k eq 'nwb') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "wb" or $k eq "nwb") 0 2 2
Condition33%1/3
$k eq "wb" or $k eq "nwb"
l!l&&r!l&&!r
002
MC/DC0%0/2
$k eq "wb" or $k eq "nwb"
$k eq "wb" $k eq "nwb"
Truth table33%1/3
A or B
A= $k eq "wb"B= $k eq "nwb"
ABresult
1X1
011
000
173 0 ▶ return undef if $n->{fold};
Branch: 1 branch
BranchTrueFalseTotal
if $n->{"fold"} 0 0 0
174 0 ▶ return $k eq 'wb' ? '(?a:\b)' : '(?a:\B)';
Branch: 1 branch
BranchTrueFalseTotal
$k eq 'wb' ? : 0 0 0
175 }
176 2 ▶ if ($k eq 'look') {
Branch: 1 branch
BranchTrueFalseTotal
if ($k eq "look") 0 2 2
177 0 ▶ return undef if $n->{behind};
Branch: 1 branch
BranchTrueFalseTotal
if $n->{"behind"} 0 0 0
178 0 ▶ my $body = _perl_regex($n->{subs}[0]) // return undef;
Condition0%0/2
_perl_regex($n->{"subs"}[0]) // (return undef)
l!l
00
MC/DC0%0/1
_perl_regex($n->{"subs"}[0]) // (return undef)
_perl_regex($n->{"subs"}[0])
Truth table0%0/2
A
A= _perl_regex($n->{"subs"}[0])
Aresult
11
00
179 0 ▶ return ($n->{negative} ? '(?!' : '(?=') . "$body)";
Branch: 1 branch
BranchTrueFalseTotal
$n->{'negative'} ? : 0 0 0
180 }
181 2 return undef;
182 }
183  
184 4 1;
« Corvus/Dialect.pm ↑ Summary Corvus/Json.pm »