STD/LazyMap.pm untested

filter: Statementstmt 0.0% 0 / 126 Branchbran 0.0% 0 / 42 Conditioncond 0.0% 0 / 15 MC/DCmcdc 0.0% 0 / 10 Subroutinesub 0.0% 0 / 21 Podpod 0.0% 0 / 15 totaltotal 0.0% 0 / 229 CC 22 SCAR 29.2
CC
22
Cov
0%
iter
56.0
lazymap
30.0
true
20.0
CRAP 18.6
1 package STD::LazyMap;
2 use 5.010;
3  
4 # STD::LazyMap.pm
5 #
6 # Copyright 2007-2010, Larry Wall
7 #
8 # You may copy this software under the terms of the Artistic License,
9 # version 2.0 or later.
10  
11 # STD::LazyMap implements backtracking for the STD::Cursor parsing engine. It does this
12 # in a very similar manner to the List monad in Haskell. Notionally, STD::Cursor
13 # processes lists of all results, however only the first result is immediately
14 # calculated; the other results are suspended, and only generated when later
15 # code needs to refer to them. The standard operation on lazy objects is to
16 # map a function over them; this function can return other objects, or lazy
17 # objects which will be lazily flattened in the result.
18  
19 # A lazy object has the iterator nature, and is destroyed by use. Lazy objects
20 # support two methods; iter returns the next value (or undef), the bool
21 # overload returns true if more values are available.
22  
23 # Lazy values can be associated with transactions. These are used in lieu
24 # of stack unwinding to implement deep cut operators; when a deep cut is
25 # performed, values are set on the transaction object, causing further iteration
26 # (i.e. backtracking) to fail for associated lazies.
27  
28 use strict;
29 use warnings;
30 no warnings 'recursion';
31  
32 use Exporter;
33  
34 our @ISA = 'Exporter';
35  
36 our @EXPORT = qw(lazymap eager);
37  
38 our $AUTOLOAD;
39  
40 # Calling an unrecognized method on a lazy delegates to the shifted value, and
41 # additionally returns the rest...
42 sub AUTOLOAD {
43 (my $meth = $AUTOLOAD) =~ s/.*:://;
44 return if $meth eq 'DESTROY';
45 print STDERR "AUTOLOAD $meth\n";
46 my $self = shift;
47 if (my ($eager) = $self->iter) {
48 return $eager->$meth(@_), $self;
49 }
50 return ();
51 }
52  
53 use overload 'bool' => 'true';
54  
55 # A lazy map represents the lazy result of a concatenating map operation.
56 # As a microoptimization, we shorten field names for the benefit of strcmp.
57 #
58 # B: the function to call to transform each incoming value; it is called in
59 # list context and it should return multiple values to create a choice
60 # point. It can also return a lazy list, which is treated as a lazy
61 # choice point.
62 # C: The values which were generated by the last block call, if it returned
63 # >1 (since iter only removes one at a time, but they don't arrive that way)
64 # L: The values input to the map which have not yet been fed to the block
65 # N: Number of values so far returned - this is used to ignore cuts if we
66 # haven't delivered our first value yet (somewhat of a hack).
67 #
68 # Values returned by a STD::LazyMap are expected to be cursors, or at least have
69 # an _xact field that can be checked for cutness.
70  
71 # Construct a lazymap - block, then a list of inputs (concatenated if lazies)
72 sub new {
73 my $class = shift;
74 my $block = shift;
75 return bless { 'B' => $block, 'C' => [], 'L' => [@_], 'N' => 0 }, $class;
76 }
77  
78 # The fundamental operation on lazies, sometimes spelled concatMap. In list
79 # context, returns the first value eagerly (this pairing is equivalent to the
80 # rolled lazymap in lazycat context).
81 sub lazymap (&@) {
82 my $block = shift;
83 return () unless @_;
84 my $lazy = bless { 'B' => $block, 'C' => [], 'L' => [@_], 'N' => 0 }, 'STD::LazyMap';
85 if (wantarray) {
86 if (my @retval = iter($lazy)) {
87 push @retval, $lazy if @{$lazy->{C}} || @{$lazy->{L}};
88 return @retval;
89 }
90 return;
91 }
92 else {
93 $lazy;
94 }
95 }
96  
97 # Destructively extract the next value from a lazy, or undef.
98 sub iter {
99 my $self = shift;
100 my $lazies = $self->{L};
101 my $called = $self->{C};
102 while (@$called or @$lazies) {
103 # pull from lazy list only when forced to
104 while (not @$called) {
105 return () unless @$lazies;
106 my $lazy = $$lazies[0];
107 # recursive lazies? delegate to lower ->iter
108 if (ref($lazy) =~ /STD::Lazy/) {
109 my $todo = $lazy->iter;
110 if (defined $todo) {
111 @$called = $self->{B}->($todo);
112 }
113 else {
114 shift @$lazies;
115 }
116 }
117 elsif (defined $lazy) { # just call our own block
118 @$called = $self->{B}->(shift @$lazies);
119 }
120 else { # undef snuck into the list somehow
121 shift @$lazies;
122 }
123 }
124  
125 # evaluating the blocks may have returned something lazy, so delegate again
126 while (@$called and ref($$called[0]) =~ /STD::Lazy/) {
127 my $really = $$called[0]->iter;
128 if ($really) {
129 unshift @$called, $really;
130 }
131 else {
132 shift @$called;
133 }
134 }
135  
136 # finally have at least one real cursor, grep for first with live transaction
137 while (@$called and ref($$called[0]) !~ /STD::Lazy/) {
138 my $candidate = shift @$called;
139 # make sure its transaction doesn't have a prior commitment
140 my $xact = $candidate->{_xact};
141 my $n = $self->{N}++;
142 return $candidate unless $xact->[-2] and $n;
143 }
144 }
145 return ();
146 }
147  
148 sub true {
149 my $self = shift();
150 my $called = $self->{C};
151 return 1 if @$called;
152 my $lazies = $self->{L};
153 return 0 unless @$lazies;
154 return 0 unless my ($c) = $self->iter;
155 unshift(@$called, $c);
156 return 1;
157 }
158  
159 # Destructively convert a lazies into a list; equivalently, places lazycat
160 # context on the interior. Only useful in list context
161 sub eager {
162 my @out;
163 while (@_) {
164 my $head = shift;
165 if (ref($head) eq 'STD::LazyMap') { # don't unroll STD::LazyConst
166 while (my ($next) = $head->iter) {
167 push @out, $next;
168 }
169 }
170 else {
171 push @out, $head;
172 }
173 }
174 # print STDERR ::Dump(@out);
175 @out;
176 }
177  
178 # STD::LazyConst produces an infinite list, which stubbornly tries the same value
179 # over and over
180 { package STD::LazyConst;
181 sub new {
182 my $self = shift;
183 my $xact = shift;
184 bless { 'K' => shift, 'X' => $xact }, 'STD::LazyConst';
185 }
186 sub true {
187 1;
188 }
189 sub iter {
190 return () if $_[0]->{X}->[-2];
191 $_[0]->{K};
192 }
193 }
194  
195 # STD::LazyRange lazily produces each value in a sequence - useful for quantifiers
196 { package STD::LazyRange;
197 sub new {
198 my $class = shift;
199 my $xact = shift;
200 my $start = shift;
201 my $end = shift;
202 bless { 'N' => $start, 'E' => $end, 'X' => $xact }, $class;
203 }
204 sub true {
205 1;
206 }
207 sub iter {
208 my $self = shift;
209 if ($self->{X}->[-2]) {
210 ()
211 }
212 elsif ((my $n = $self->{N}++) <= $self->{E}) {
213 $n;
214 }
215 else {
216 ();
217 }
218 }
219 }
220  
221 # Like above, but reverse
222 { package STD::LazyRangeRev;
223 sub new {
224 my $class = shift;
225 my $xact = shift;
226 my $start = shift;
227 my $end = shift;
228 bless { 'N' => $start, 'E' => $end, 'X' => $xact }, $class;
229 }
230 sub true {
231 1;
232 }
233 sub iter {
234 my $self = shift;
235 if ($self->{X}->[-2]) {
236 ()
237 }
238 elsif ((my $n = $self->{N}--) >= $self->{E}) {
239 $n;
240 }
241 else {
242 ();
243 }
244 }
245 }
246  
247 1;