| 1 | # | ||||||||||||
| 2 | # Copyright (c) 2015-2021 Christian Jaeger, copying@christianjaeger.ch | ||||||||||||
| 3 | # | ||||||||||||
| 4 | # This is free software, offered under either the same terms as perl 5 | ||||||||||||
| 5 | # or the terms of the Artistic License version 2 or the terms of the | ||||||||||||
| 6 | # MIT License (Expat version). See the file COPYING.md that came | ||||||||||||
| 7 | # bundled with this file. | ||||||||||||
| 8 | # | ||||||||||||
| 9 | |||||||||||||
| 10 | =head1 NAME | ||||||||||||
| 11 | |||||||||||||
| 12 | FP::Memoizing - a functional memoize | ||||||||||||
| 13 | |||||||||||||
| 14 | =head1 SYNOPSIS | ||||||||||||
| 15 | |||||||||||||
| 16 | 1 | ▶ | use FP::Memoizing qw(memoizing memoizing_to_dir); | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 17 | use Chj::tempdir; | ||||||||||||
| 18 | my $tmp = do{ mkdir ".tmp"; tempdir ".tmp/" }; | ||||||||||||
| 19 | |||||||||||||
| 20 | my $count = 0; | ||||||||||||
| 21 | sub f { $count++; $_[0] * 5 } | ||||||||||||
| 22 | |||||||||||||
| 23 | *fm = memoizing \&f; # memoize in process memory | ||||||||||||
| 24 | *fm2 = memoizing_to_dir $tmp, \&f; # memoize to files in ".foo/" | ||||||||||||
| 25 | |||||||||||||
| 26 | is fm(3), 15; | ||||||||||||
| 27 | is $count, 1; | ||||||||||||
| 28 | is fm(3), 15; | ||||||||||||
| 29 | is $count, 1; | ||||||||||||
| 30 | is fm(2), 10; | ||||||||||||
| 31 | is $count, 2; | ||||||||||||
| 32 | is fm2(3), 15; | ||||||||||||
| 33 | is $count, 3; | ||||||||||||
| 34 | is fm2(3), 15; | ||||||||||||
| 35 | is $count, 3; | ||||||||||||
| 36 | |||||||||||||
| 37 | |||||||||||||
| 38 | =head1 DESCRIPTION | ||||||||||||
| 39 | |||||||||||||
| 40 | |||||||||||||
| 41 | =head1 TODO | ||||||||||||
| 42 | |||||||||||||
| 43 | No locking whatsoever is currently being done. | ||||||||||||
| 44 | |||||||||||||
| 45 | Also, serializes twice in different ways, for the key and the actual | ||||||||||||
| 46 | storage. Could Storable be used for the key as well? | ||||||||||||
| 47 | |||||||||||||
| 48 | =head1 NOTE | ||||||||||||
| 49 | |||||||||||||
| 50 | This is alpha software! Read the status section in the package README | ||||||||||||
| 51 | or on the L<website|http://functional-perl.org/>. | ||||||||||||
| 52 | |||||||||||||
| 53 | =cut | ||||||||||||
| 54 | |||||||||||||
| 55 | package FP::Memoizing; | ||||||||||||
| 56 | 3 | ▶ | use strict; | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 57 | 3 | ▶ | use warnings; | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 58 | 3 | ▶ | use warnings FATAL => 'uninitialized'; | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 59 | 3 | ▶ | use Exporter "import"; | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 60 | |||||||||||||
| 61 | 3 | our @EXPORT = qw(memoizing); | |||||||||||
| 62 | 3 | our @EXPORT_OK = qw(memoizing_to_dir); | |||||||||||
| 63 | 3 | our %EXPORT_TAGS = (all => [@EXPORT, @EXPORT_OK]); | |||||||||||
| 64 | |||||||||||||
| 65 | 3 | ▶ | use Chj::TEST; | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 66 | 3 | ▶ | use Storable qw(nfreeze nstore_fd fd_retrieve); | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 67 | 3 | ▶ | use Digest; | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 68 | 3 | ▶ | use FP::Hash qw(hash_cache); | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 69 | 3 | ▶ | use FP::Carp; | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 70 | |||||||||||||
| 71 | #use Chj::TerseDumper; | ||||||||||||
| 72 | |||||||||||||
| 73 | # ---------------------------------------------------------------- | ||||||||||||
| 74 | # For keys: | ||||||||||||
| 75 | |||||||||||||
| 76 | # sub xnfreeze { | ||||||||||||
| 77 | # @_ == 1 or die "wrong number of arguments"; | ||||||||||||
| 78 | # nfreeze ($_[0]) | ||||||||||||
| 79 | # // die "can't freeze this: ".TerseDumper ($_[0]); | ||||||||||||
| 80 | # } | ||||||||||||
| 81 | |||||||||||||
| 82 | 24 | ▶ | sub xncanonicalfreeze { | ||||||||||
|
Subroutine
xncanonicalfreeze: called CC=2 SCAR=7.1
Pod
undocumented
| |||||||||||||
| 83 | 24 | ▶ | @_ == 1 or fp_croak_arity 1; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 84 | 24 | local $Storable::canonical = 1; | |||||||||||
| 85 | 24 | nfreeze($_[0]) | |||||||||||
| 86 | } | ||||||||||||
| 87 | |||||||||||||
| 88 | #sub xthaw { | ||||||||||||
| 89 | # @_ == 1 or die "wrong number of arguments"; | ||||||||||||
| 90 | # thaw ($_[0]) | ||||||||||||
| 91 | # // die "corrupted file, can't thaw"; | ||||||||||||
| 92 | #} | ||||||||||||
| 93 | |||||||||||||
| 94 | 3 | our $freeze_args = \&xncanonicalfreeze; | |||||||||||
| 95 | |||||||||||||
| 96 | # XX use TerseDumper instead, to allow for unserializable | ||||||||||||
| 97 | # values? But, says things like 'sub { "DUMMY" }' which isn't unique | ||||||||||||
| 98 | # for subs, thus nope, won't work either. Perl is a mess in this area, | ||||||||||||
| 99 | # right? (Plays nice with the OS? But then doesn't provide for a well | ||||||||||||
| 100 | # thought out data exchange.) | ||||||||||||
| 101 | |||||||||||||
| 102 | # XX what about promises? die, or force them? Don't just be silent | ||||||||||||
| 103 | # please | ||||||||||||
| 104 | |||||||||||||
| 105 | 26 | ▶ | our $digest = sub { | ||||||||||
|
Subroutine
__ANON__: called CC=2 SCAR=7.0
| |||||||||||||
| 106 | 26 | ▶ | @_ == 1 or fp_croak_arity 1; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 107 | 26 | my $ctx = Digest->new("SHA-256"); | |||||||||||
| 108 | 23 | $ctx->add($_[0]); | |||||||||||
| 109 | 23 | my $d = $ctx->b64digest; | |||||||||||
| 110 | 23 | $d =~ tr|/.|--|; | |||||||||||
| 111 | 23 | $d | |||||||||||
| 112 | 3 | }; | |||||||||||
| 113 | |||||||||||||
| 114 | 23 | ▶ | our $digest_args = sub { | ||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||
| 115 | 23 | &$digest(&$freeze_args([@_])) | |||||||||||
| 116 | 3 | }; | |||||||||||
| 117 | |||||||||||||
| 118 | # ---------------------------------------------------------------- | ||||||||||||
| 119 | # For results: | ||||||||||||
| 120 | |||||||||||||
| 121 | # Just as it is the usual pain with Storable: | ||||||||||||
| 122 | |||||||||||||
| 123 | # 1. values must be wrapped in an array; | ||||||||||||
| 124 | # 2. OS errors versus format errors? No go, right? | ||||||||||||
| 125 | |||||||||||||
| 126 | 6 | ▶ | sub fh_xnstore { | ||||||||||
|
Subroutine
fh_xnstore: called CC=3 SCAR=12.0
Pod
undocumented
| |||||||||||||
| 127 | 6 | ▶ | @_ == 2 or fp_croak_arity 2; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 128 | |||||||||||||
| 129 | # fh, arrayref | ||||||||||||
| 130 | 6 | ▶ | nstore_fd($_[1], $_[0]) | ||||||||||
|
Condition50%1/2
nstore_fd($_[1], $_[0]) // die("nstore_fd had SOME error (perhaps this?: $!)")
MC/DC0%0/1
nstore_fd($_[1], $_[0]) // die("nstore_fd had SOME error (perhaps this?: $!)")
nstore_fd($_[1], $_[0])
Truth table50%1/2
A
A= nstore_fd($_[1], $_[0])
| |||||||||||||
| 131 | // die "nstore_fd had SOME error (perhaps this?: $!)"; | ||||||||||||
| 132 | |||||||||||||
| 133 | # << The routine returns "undef" for I/O problems or other internal | ||||||||||||
| 134 | # error, a true value otherwise. Serious errors are propagated as | ||||||||||||
| 135 | # a "die" exception. >> So, what is a serious error, please, and | ||||||||||||
| 136 | # undef doesn't mean I can rely on the error message being in $!, | ||||||||||||
| 137 | # either. Sigh. | ||||||||||||
| 138 | } | ||||||||||||
| 139 | |||||||||||||
| 140 | 5 | ▶ | sub fh_xdeserialize { | ||||||||||
|
Subroutine
fh_xdeserialize: called CC=3 SCAR=12.0
Pod
undocumented
| |||||||||||||
| 141 | 5 | ▶ | @_ == 1 or fp_croak_arity 1; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 142 | 5 | ▶ | fd_retrieve($_[0]) // die "SOME retrieval error"; | ||||||||||
|
Condition50%1/2
fd_retrieve($_[0]) // die("SOME retrieval error")
MC/DC0%0/1
fd_retrieve($_[0]) // die("SOME retrieval error")
fd_retrieve($_[0])
Truth table50%1/2
A
A= fd_retrieve($_[0])
| |||||||||||||
| 143 | } | ||||||||||||
| 144 | |||||||||||||
| 145 | # ---------------------------------------------------------------- | ||||||||||||
| 146 | |||||||||||||
| 147 | 8 | ▶ | sub memoizing_ { | ||||||||||
|
Subroutine
memoizing_: called CC=2 SCAR=7.0
Pod
undocumented
| |||||||||||||
| 148 | 8 | ▶ | @_ == 3 or fp_croak_arity 3; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 149 | 8 | my ($fn, $cache, $getcache) = @_; | |||||||||||
| 150 | 23 | ▶ | sub { | ||||||||||
|
Subroutine
__ANON__: called CC=4 SCAR=13.9
| |||||||||||||
| 151 | 23 | my @args = @_; | |||||||||||
| 152 | 23 | my $wantarray = wantarray; ## no critic | |||||||||||
| 153 | 23 | ▶ | defined $wantarray or die "using a memoizing function in void context"; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 154 | |||||||||||||
| 155 | # Can't reuse the result from an array context in a scalar | ||||||||||||
| 156 | # context, since we can't assume that $fn would return the | ||||||||||||
| 157 | # last value in scalar context, thus make the context part of | ||||||||||||
| 158 | # the key. | ||||||||||||
| 159 | 23 | ▶ | my $key = ($wantarray ? "n" : "1") . &$digest_args(@_); | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 160 | |||||||||||||
| 161 | my $vals = &$getcache($cache, $key, | ||||||||||||
| 162 | 23 | ▶ | sub { [$wantarray ? &$fn(@args) : scalar &$fn(@args)] }); | ||||||||||
|
Subroutine
__ANON__: called CC=2 SCAR=6.9
Branch: 1 branch
| |||||||||||||
| 163 | |||||||||||||
| 164 | 23 | ▶ | $wantarray ? @$vals : $$vals[-1] | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 165 | } | ||||||||||||
| 166 | 8 | } | |||||||||||
| 167 | |||||||||||||
| 168 | 3 | ▶ | sub memoizing { | ||||||||||
|
Subroutine
memoizing: called CC=2 SCAR=7.1
Pod
undocumented
| |||||||||||||
| 169 | 3 | ▶ | @_ == 1 or fp_croak_arity 1; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 170 | 3 | my ($fn) = @_; | |||||||||||
| 171 | 3 | memoizing_ $fn, +{}, \&hash_cache | |||||||||||
| 172 | } | ||||||||||||
| 173 | |||||||||||||
| 174 | 3 | ▶ | use Chj::xopen qw(perhaps_xopen_read); | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 175 | 3 | ▶ | use Chj::xtmpfile; | ||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||
| 176 | |||||||||||||
| 177 | # Same API as hash_cache (and like it, only works in scalar context). | ||||||||||||
| 178 | # CAREFUL, $k is not checked for subversive values ("../" etc.), only | ||||||||||||
| 179 | # use with hashed keys or so! | ||||||||||||
| 180 | |||||||||||||
| 181 | 11 | ▶ | sub file_cache { | ||||||||||
|
Subroutine
file_cache: called CC=3 SCAR=11.0
Pod
undocumented
| |||||||||||||
| 182 | 11 | ▶ | @_ == 3 or fp_croak_arity 3; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 183 | 11 | my ($basepath, $k, $generate) = @_; | |||||||||||
| 184 | |||||||||||||
| 185 | 11 | my $path = $basepath . $k; | |||||||||||
| 186 | |||||||||||||
| 187 | 11 | ▶ | if (my ($in) = perhaps_xopen_read $path) { | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 188 | 5 | my $val = fh_xdeserialize($in); | |||||||||||
| 189 | 5 | $in->xclose; | |||||||||||
| 190 | 5 | $val | |||||||||||
| 191 | } else { | ||||||||||||
| 192 | 6 | my $out = xtmpfile $path; | |||||||||||
| 193 | 6 | my $val = &$generate(); | |||||||||||
| 194 | 6 | fh_xnstore($out, $val); | |||||||||||
| 195 | 6 | $out->xclose; | |||||||||||
| 196 | 6 | $out->xputback(0444); | |||||||||||
| 197 | 6 | $val | |||||||||||
| 198 | } | ||||||||||||
| 199 | } | ||||||||||||
| 200 | |||||||||||||
| 201 | 5 | ▶ | sub memoizing_to_dir { | ||||||||||
|
Subroutine
memoizing_to_dir: called CC=3 SCAR=11.4
Pod
undocumented
| |||||||||||||
| 202 | 5 | ▶ | @_ == 2 or fp_croak_arity 2; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 203 | 5 | my ($dirpath, $f) = @_; | |||||||||||
| 204 | 5 | ▶ | $dirpath .= "/" unless $dirpath =~ /\/$/s; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 205 | 5 | memoizing_ $f, $dirpath, \&file_cache | |||||||||||
| 206 | } | ||||||||||||
| 207 | |||||||||||||
| 208 | 6 | ▶ | sub tests_for { | ||||||||||
|
Subroutine
tests_for: called CC=2 SCAR=6.9
Pod
undocumented
| |||||||||||||
| 209 | 6 | ▶ | @_ == 1 or fp_croak_arity 1; | ||||||||||
|
Branch: 1 branch
| |||||||||||||
| 210 | 6 | my ($memoizing) = @_; | |||||||||||
| 211 | |||||||||||||
| 212 | 6 | my ($t_count, $f); | |||||||||||
| 213 | |||||||||||||
| 214 | 2 | ▶ | TEST { | ||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||
| 215 | 2 | ▶ | $f = &$memoizing(sub { my ($x) = @_; $t_count++; ($x, $x * $x) }); | ||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||
| 216 | 2 | [[&$f(1)], $t_count] | |||||||||||
| 217 | } | ||||||||||||
| 218 | 6 | [[1, 1], 1]; | |||||||||||
| 219 | |||||||||||||
| 220 | 2 | ▶ | TEST { [[&$f(2)], $t_count] } | ||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||
| 221 | 6 | [[2, 4], 2]; | |||||||||||
| 222 | |||||||||||||
| 223 | 2 | ▶ | TEST { [[&$f(2)], $t_count] } | ||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||
| 224 | 6 | [[2, 4], 2]; | |||||||||||
| 225 | |||||||||||||
| 226 | 2 | ▶ | TEST { [[scalar &$f(2)], $t_count] } | ||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||
| 227 | 6 | [[4], 3]; | |||||||||||
| 228 | |||||||||||||
| 229 | 2 | ▶ | TEST { | ||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||
| 230 | 2 | ▶ | my $f = &$memoizing(sub { $t_count++; undef }); | ||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||
| 231 | 2 | [&$f(undef), &$f(undef), scalar &$f(undef), scalar &$f(undef)] | |||||||||||
| 232 | } | ||||||||||||
| 233 | 6 | [undef, undef, undef, undef]; | |||||||||||
| 234 | |||||||||||||
| 235 | 2 | ▶ | TEST { | ||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||
| 236 | 2 | my $r = [[scalar &$f(2)], $t_count]; | |||||||||||
| 237 | 2 | undef $f; | |||||||||||
| 238 | 2 | undef $t_count; | |||||||||||
| 239 | 2 | $r | |||||||||||
| 240 | } | ||||||||||||
| 241 | 6 | [[4], 5]; | |||||||||||
| 242 | } | ||||||||||||
| 243 | |||||||||||||
| 244 | 3 | tests_for \&memoizing; | |||||||||||
| 245 | |||||||||||||
| 246 | { | ||||||||||||
| 247 | 3 | my $tdir = ".FP-Memoizing-tests"; | |||||||||||
| 248 | |||||||||||||
| 249 | 1 | ▶ | TEST { | ||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||
| 250 | 1 | mkdir $tdir; | |||||||||||
| 251 | } | ||||||||||||
| 252 | 3 | 1; | |||||||||||
| 253 | |||||||||||||
| 254 | 2 | ▶ | tests_for sub { | ||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||
| 255 | 2 | my ($f) = @_; | |||||||||||
| 256 | 2 | &memoizing_to_dir($tdir, $f); | |||||||||||
| 257 | 3 | }; | |||||||||||
| 258 | |||||||||||||
| 259 | 1 | ▶ | TEST { | ||||||||||
|
Subroutine
__ANON__: called CC=1 SCAR=0.0
| |||||||||||||
| 260 | 1 | require File::Path; | |||||||||||
| 261 | 1 | File::Path::remove_tree $tdir; | |||||||||||
| 262 | } | ||||||||||||
| 263 | 3 | 6; | |||||||||||
| 264 | } | ||||||||||||
| 265 | |||||||||||||
| 266 | 3 | 1 | |||||||||||