1 // Written in the D programming language.
2
3 /**
4 Functions that manipulate other functions.
5
6 This module provides functions for compile time function composition. These
7 functions are helpful when constructing predicates for the algorithms in
8 $(MREF std, algorithm) or $(MREF std, range).
9
10 $(SCRIPT inhibitQuickIndex = 1;)
11 $(DIVC quickindex,
12 $(BOOKTABLE ,
13 $(TR $(TH Function Name) $(TH Description)
14 )
15 $(TR $(TD $(LREF adjoin))
16 $(TD Joins a couple of functions into one that executes the original
17 functions independently and returns a tuple with all the results.
18 ))
19 $(TR $(TD $(LREF compose), $(LREF pipe))
20 $(TD Join a couple of functions into one that executes the original
21 functions one after the other, using one function's result for the next
22 function's argument.
23 ))
24 $(TR $(TD $(LREF lessThan), $(LREF greaterThan), $(LREF equalTo))
25 $(TD Ready-made predicate functions to compare two values.
26 ))
27 $(TR $(TD $(LREF memoize))
28 $(TD Creates a function that caches its result for fast re-evaluation.
29 ))
30 $(TR $(TD $(LREF not))
31 $(TD Creates a function that negates another.
32 ))
33 $(TR $(TD $(LREF partial))
34 $(TD Creates a function that binds the first argument of a given function
35 to a given value.
36 ))
37 $(TR $(TD $(LREF curry))
38 $(TD Converts a multi-argument function into a series of single-argument
39 functions. f(x, y) == curry(f)(x)(y)
40 ))
41 $(TR $(TD $(LREF reverseArgs))
42 $(TD Predicate that reverses the order of its arguments.
43 ))
44 $(TR $(TD $(LREF toDelegate))
45 $(TD Converts a callable to a delegate.
46 ))
47 $(TR $(TD $(LREF unaryFun), $(LREF binaryFun))
48 $(TD Create a unary or binary function from a string. Most often
49 used when defining algorithms on ranges.
50 ))
51 ))
52
53 Copyright: Copyright Andrei Alexandrescu 2008 - 2009.
54 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
55 Authors: $(HTTP erdani.org, Andrei Alexandrescu)
56 Source: $(PHOBOSSRC std/functional.d)
57 */
58 /*
59 Copyright Andrei Alexandrescu 2008 - 2009.
60 Distributed under the Boost Software License, Version 1.0.
61 (See accompanying file LICENSE_1_0.txt or copy at
62 http://www.boost.org/LICENSE_1_0.txt)
63 */
64 module std.functional;
65
66 import std.meta : AliasSeq, Reverse;
67 import std.traits : isCallable, Parameters;
68
69 import std.internal.attributes : betterC;
70
needOpCallAlias(alias fun)71 private template needOpCallAlias(alias fun)
72 {
73 /* Determine whether or not unaryFun and binaryFun need to alias to fun or
74 * fun.opCall. Basically, fun is a function object if fun(...) compiles. We
75 * want is(unaryFun!fun) (resp., is(binaryFun!fun)) to be true if fun is
76 * any function object. There are 4 possible cases:
77 *
78 * 1) fun is the type of a function object with static opCall;
79 * 2) fun is an instance of a function object with static opCall;
80 * 3) fun is the type of a function object with non-static opCall;
81 * 4) fun is an instance of a function object with non-static opCall.
82 *
83 * In case (1), is(unaryFun!fun) should compile, but does not if unaryFun
84 * aliases itself to fun, because typeof(fun) is an error when fun itself
85 * is a type. So it must be aliased to fun.opCall instead. All other cases
86 * should be aliased to fun directly.
87 */
88 static if (is(typeof(fun.opCall) == function))
89 {
90 enum needOpCallAlias = !is(typeof(fun)) && __traits(compiles, () {
91 return fun(Parameters!fun.init);
92 });
93 }
94 else
95 enum needOpCallAlias = false;
96 }
97
98 /**
99 Transforms a `string` representing an expression into a unary
100 function. The `string` must either use symbol name `a` as
101 the parameter or provide the symbol via the `parmName` argument.
102
103 Params:
104 fun = a `string` or a callable
105 parmName = the name of the parameter if `fun` is a string. Defaults
106 to `"a"`.
107 Returns:
108 If `fun` is a `string`, a new single parameter function
109
110 If `fun` is not a `string`, an alias to `fun`.
111 */
112 template unaryFun(alias fun, string parmName = "a")
113 {
114 static if (is(typeof(fun) : string))
115 {
116 static if (!fun._ctfeMatchUnary(parmName))
117 {
118 import std.algorithm, std.conv, std.exception, std.math, std.range, std.string;
119 import std.meta, std.traits, std.typecons;
120 }
unaryFun(ElementType)121 auto unaryFun(ElementType)(auto ref ElementType __a)
122 {
123 mixin("alias " ~ parmName ~ " = __a ;");
124 return mixin(fun);
125 }
126 }
127 else static if (needOpCallAlias!fun)
128 {
129 // https://issues.dlang.org/show_bug.cgi?id=9906
130 alias unaryFun = fun.opCall;
131 }
132 else
133 {
134 alias unaryFun = fun;
135 }
136 }
137
138 ///
139 @safe unittest
140 {
141 // Strings are compiled into functions:
142 alias isEven = unaryFun!("(a & 1) == 0");
143 assert(isEven(2) && !isEven(1));
144 }
145
146 @safe unittest
147 {
f1(int a)148 static int f1(int a) { return a + 1; }
149 static assert(is(typeof(unaryFun!(f1)(1)) == int));
150 assert(unaryFun!(f1)(41) == 42);
f2(int a)151 int f2(int a) { return a + 1; }
152 static assert(is(typeof(unaryFun!(f2)(1)) == int));
153 assert(unaryFun!(f2)(41) == 42);
154 assert(unaryFun!("a + 1")(41) == 42);
155 //assert(unaryFun!("return a + 1;")(41) == 42);
156
157 int num = 41;
158 assert(unaryFun!"a + 1"(num) == 42);
159
160 // https://issues.dlang.org/show_bug.cgi?id=9906
161 struct Seen
162 {
opCallSeen163 static bool opCall(int n) { return true; }
164 }
165 static assert(needOpCallAlias!Seen);
166 static assert(is(typeof(unaryFun!Seen(1))));
167 assert(unaryFun!Seen(1));
168
169 Seen s;
170 static assert(!needOpCallAlias!s);
171 static assert(is(typeof(unaryFun!s(1))));
172 assert(unaryFun!s(1));
173
174 struct FuncObj
175 {
opCallFuncObj176 bool opCall(int n) { return true; }
177 }
178 FuncObj fo;
179 static assert(!needOpCallAlias!fo);
180 static assert(is(typeof(unaryFun!fo)));
181 assert(unaryFun!fo(1));
182
183 // Function object with non-static opCall can only be called with an
184 // instance, not with merely the type.
185 static assert(!is(typeof(unaryFun!FuncObj)));
186 }
187
188 /**
189 Transforms a `string` representing an expression into a binary function. The
190 `string` must either use symbol names `a` and `b` as the parameters or
191 provide the symbols via the `parm1Name` and `parm2Name` arguments.
192
193 Params:
194 fun = a `string` or a callable
195 parm1Name = the name of the first parameter if `fun` is a string.
196 Defaults to `"a"`.
197 parm2Name = the name of the second parameter if `fun` is a string.
198 Defaults to `"b"`.
199 Returns:
200 If `fun` is not a string, `binaryFun` aliases itself away to
201 `fun`.
202 */
203 template binaryFun(alias fun, string parm1Name = "a",
204 string parm2Name = "b")
205 {
206 static if (is(typeof(fun) : string))
207 {
208 static if (!fun._ctfeMatchBinary(parm1Name, parm2Name))
209 {
210 import std.algorithm, std.conv, std.exception, std.math, std.range, std.string;
211 import std.meta, std.traits, std.typecons;
212 }
binaryFun(ElementType1,ElementType2)213 auto binaryFun(ElementType1, ElementType2)
214 (auto ref ElementType1 __a, auto ref ElementType2 __b)
215 {
216 mixin("alias "~parm1Name~" = __a ;");
217 mixin("alias "~parm2Name~" = __b ;");
218 return mixin(fun);
219 }
220 }
221 else static if (needOpCallAlias!fun)
222 {
223 // https://issues.dlang.org/show_bug.cgi?id=9906
224 alias binaryFun = fun.opCall;
225 }
226 else
227 {
228 alias binaryFun = fun;
229 }
230 }
231
232 ///
233 @safe unittest
234 {
235 alias less = binaryFun!("a < b");
236 assert(less(1, 2) && !less(2, 1));
237 alias greater = binaryFun!("a > b");
238 assert(!greater("1", "2") && greater("2", "1"));
239 }
240
241 @safe unittest
242 {
f1(int a,string b)243 static int f1(int a, string b) { return a + 1; }
244 static assert(is(typeof(binaryFun!(f1)(1, "2")) == int));
245 assert(binaryFun!(f1)(41, "a") == 42);
f2(int a,string b)246 string f2(int a, string b) { return b ~ "2"; }
247 static assert(is(typeof(binaryFun!(f2)(1, "1")) == string));
248 assert(binaryFun!(f2)(1, "4") == "42");
249 assert(binaryFun!("a + b")(41, 1) == 42);
250 //@@BUG
251 //assert(binaryFun!("return a + b;")(41, 1) == 42);
252
253 // https://issues.dlang.org/show_bug.cgi?id=9906
254 struct Seen
255 {
opCallSeen256 static bool opCall(int x, int y) { return true; }
257 }
258 static assert(is(typeof(binaryFun!Seen)));
259 assert(binaryFun!Seen(1,1));
260
261 struct FuncObj
262 {
opCallFuncObj263 bool opCall(int x, int y) { return true; }
264 }
265 FuncObj fo;
266 static assert(!needOpCallAlias!fo);
267 static assert(is(typeof(binaryFun!fo)));
268 assert(unaryFun!fo(1,1));
269
270 // Function object with non-static opCall can only be called with an
271 // instance, not with merely the type.
272 static assert(!is(typeof(binaryFun!FuncObj)));
273 }
274
275 // skip all ASCII chars except a .. z, A .. Z, 0 .. 9, '_' and '.'.
_ctfeSkipOp(ref string op)276 private uint _ctfeSkipOp(ref string op)
277 {
278 if (!__ctfe) assert(false);
279 import std.ascii : isASCII, isAlphaNum;
280 immutable oldLength = op.length;
281 while (op.length)
282 {
283 immutable front = op[0];
284 if (front.isASCII() && !(front.isAlphaNum() || front == '_' || front == '.'))
285 op = op[1..$];
286 else
287 break;
288 }
289 return oldLength != op.length;
290 }
291
292 // skip all digits
_ctfeSkipInteger(ref string op)293 private uint _ctfeSkipInteger(ref string op)
294 {
295 if (!__ctfe) assert(false);
296 import std.ascii : isDigit;
297 immutable oldLength = op.length;
298 while (op.length)
299 {
300 immutable front = op[0];
301 if (front.isDigit())
302 op = op[1..$];
303 else
304 break;
305 }
306 return oldLength != op.length;
307 }
308
309 // skip name
_ctfeSkipName(ref string op,string name)310 private uint _ctfeSkipName(ref string op, string name)
311 {
312 if (!__ctfe) assert(false);
313 if (op.length >= name.length && op[0 .. name.length] == name)
314 {
315 op = op[name.length..$];
316 return 1;
317 }
318 return 0;
319 }
320
321 // returns 1 if `fun` is trivial unary function
_ctfeMatchUnary(string fun,string name)322 private uint _ctfeMatchUnary(string fun, string name)
323 {
324 if (!__ctfe) assert(false);
325 fun._ctfeSkipOp();
326 for (;;)
327 {
328 immutable h = fun._ctfeSkipName(name) + fun._ctfeSkipInteger();
329 if (h == 0)
330 {
331 fun._ctfeSkipOp();
332 break;
333 }
334 else if (h == 1)
335 {
336 if (!fun._ctfeSkipOp())
337 break;
338 }
339 else
340 return 0;
341 }
342 return fun.length == 0;
343 }
344
345 @safe unittest
346 {
347 static assert(!_ctfeMatchUnary("sqrt(ё)", "ё"));
348 static assert(!_ctfeMatchUnary("ё.sqrt", "ё"));
349 static assert(!_ctfeMatchUnary(".ё+ё", "ё"));
350 static assert(!_ctfeMatchUnary("_ё+ё", "ё"));
351 static assert(!_ctfeMatchUnary("ёё", "ё"));
352 static assert(_ctfeMatchUnary("a+a", "a"));
353 static assert(_ctfeMatchUnary("a + 10", "a"));
354 static assert(_ctfeMatchUnary("4 == a", "a"));
355 static assert(_ctfeMatchUnary("2 == a", "a"));
356 static assert(_ctfeMatchUnary("1 != a", "a"));
357 static assert(_ctfeMatchUnary("a != 4", "a"));
358 static assert(_ctfeMatchUnary("a< 1", "a"));
359 static assert(_ctfeMatchUnary("434 < a", "a"));
360 static assert(_ctfeMatchUnary("132 > a", "a"));
361 static assert(_ctfeMatchUnary("123 >a", "a"));
362 static assert(_ctfeMatchUnary("a>82", "a"));
363 static assert(_ctfeMatchUnary("ё>82", "ё"));
364 static assert(_ctfeMatchUnary("ё[ё(ё)]", "ё"));
365 static assert(_ctfeMatchUnary("ё[21]", "ё"));
366 }
367
368 // returns 1 if `fun` is trivial binary function
_ctfeMatchBinary(string fun,string name1,string name2)369 private uint _ctfeMatchBinary(string fun, string name1, string name2)
370 {
371 if (!__ctfe) assert(false);
372 fun._ctfeSkipOp();
373 for (;;)
374 {
375 immutable h = fun._ctfeSkipName(name1) + fun._ctfeSkipName(name2) + fun._ctfeSkipInteger();
376 if (h == 0)
377 {
378 fun._ctfeSkipOp();
379 break;
380 }
381 else if (h == 1)
382 {
383 if (!fun._ctfeSkipOp())
384 break;
385 }
386 else
387 return 0;
388 }
389 return fun.length == 0;
390 }
391
392 @safe unittest
393 {
394
395 static assert(!_ctfeMatchBinary("sqrt(ё)", "ё", "b"));
396 static assert(!_ctfeMatchBinary("ё.sqrt", "ё", "b"));
397 static assert(!_ctfeMatchBinary(".ё+ё", "ё", "b"));
398 static assert(!_ctfeMatchBinary("_ё+ё", "ё", "b"));
399 static assert(!_ctfeMatchBinary("ёё", "ё", "b"));
400 static assert(_ctfeMatchBinary("a+a", "a", "b"));
401 static assert(_ctfeMatchBinary("a + 10", "a", "b"));
402 static assert(_ctfeMatchBinary("4 == a", "a", "b"));
403 static assert(_ctfeMatchBinary("2 == a", "a", "b"));
404 static assert(_ctfeMatchBinary("1 != a", "a", "b"));
405 static assert(_ctfeMatchBinary("a != 4", "a", "b"));
406 static assert(_ctfeMatchBinary("a< 1", "a", "b"));
407 static assert(_ctfeMatchBinary("434 < a", "a", "b"));
408 static assert(_ctfeMatchBinary("132 > a", "a", "b"));
409 static assert(_ctfeMatchBinary("123 >a", "a", "b"));
410 static assert(_ctfeMatchBinary("a>82", "a", "b"));
411 static assert(_ctfeMatchBinary("ё>82", "ё", "q"));
412 static assert(_ctfeMatchBinary("ё[ё(10)]", "ё", "q"));
413 static assert(_ctfeMatchBinary("ё[21]", "ё", "q"));
414
415 static assert(!_ctfeMatchBinary("sqrt(ё)+b", "b", "ё"));
416 static assert(!_ctfeMatchBinary("ё.sqrt-b", "b", "ё"));
417 static assert(!_ctfeMatchBinary(".ё+b", "b", "ё"));
418 static assert(!_ctfeMatchBinary("_b+ё", "b", "ё"));
419 static assert(!_ctfeMatchBinary("ba", "b", "a"));
420 static assert(_ctfeMatchBinary("a+b", "b", "a"));
421 static assert(_ctfeMatchBinary("a + b", "b", "a"));
422 static assert(_ctfeMatchBinary("b == a", "b", "a"));
423 static assert(_ctfeMatchBinary("b == a", "b", "a"));
424 static assert(_ctfeMatchBinary("b != a", "b", "a"));
425 static assert(_ctfeMatchBinary("a != b", "b", "a"));
426 static assert(_ctfeMatchBinary("a< b", "b", "a"));
427 static assert(_ctfeMatchBinary("b < a", "b", "a"));
428 static assert(_ctfeMatchBinary("b > a", "b", "a"));
429 static assert(_ctfeMatchBinary("b >a", "b", "a"));
430 static assert(_ctfeMatchBinary("a>b", "b", "a"));
431 static assert(_ctfeMatchBinary("ё>b", "b", "ё"));
432 static assert(_ctfeMatchBinary("b[ё(-1)]", "b", "ё"));
433 static assert(_ctfeMatchBinary("ё[-21]", "b", "ё"));
434 }
435
436 //undocumented
437 template safeOp(string S)
438 if (S=="<"||S==">"||S=="<="||S==">="||S=="=="||S=="!=")
439 {
440 import std.traits : isIntegral;
441 private bool unsafeOp(ElementType1, ElementType2)(ElementType1 a, ElementType2 b) pure
442 if (isIntegral!ElementType1 && isIntegral!ElementType2)
443 {
444 import std.traits : CommonType;
445 alias T = CommonType!(ElementType1, ElementType2);
446 return mixin("cast(T)a "~S~" cast(T) b");
447 }
448
safeOp(T0,T1)449 bool safeOp(T0, T1)(auto ref T0 a, auto ref T1 b)
450 {
451 import std.traits : mostNegative;
452 static if (isIntegral!T0 && isIntegral!T1 &&
453 (mostNegative!T0 < 0) != (mostNegative!T1 < 0))
454 {
455 static if (S == "<=" || S == "<")
456 {
457 static if (mostNegative!T0 < 0)
458 immutable result = a < 0 || unsafeOp(a, b);
459 else
460 immutable result = b >= 0 && unsafeOp(a, b);
461 }
462 else
463 {
464 static if (mostNegative!T0 < 0)
465 immutable result = a >= 0 && unsafeOp(a, b);
466 else
467 immutable result = b < 0 || unsafeOp(a, b);
468 }
469 }
470 else
471 {
472 static assert(is(typeof(mixin("a "~S~" b"))),
473 "Invalid arguments: Cannot compare types " ~ T0.stringof ~ " and " ~ T1.stringof ~ ".");
474
475 immutable result = mixin("a "~S~" b");
476 }
477 return result;
478 }
479 }
480
481 @safe unittest //check user defined types
482 {
483 import std.algorithm.comparison : equal;
484 struct Foo
485 {
486 int a;
opEqualsFoo487 auto opEquals(Foo foo)
488 {
489 return a == foo.a;
490 }
491 }
492 assert(safeOp!"!="(Foo(1), Foo(2)));
493 }
494
495 /**
496 Predicate that returns $(D_PARAM a < b).
497 Correctly compares signed and unsigned integers, ie. -1 < 2U.
498 */
499 alias lessThan = safeOp!"<";
500
501 ///
502 pure @safe @nogc nothrow unittest
503 {
504 assert(lessThan(2, 3));
505 assert(lessThan(2U, 3U));
506 assert(lessThan(2, 3.0));
507 assert(lessThan(-2, 3U));
508 assert(lessThan(2, 3U));
509 assert(!lessThan(3U, -2));
510 assert(!lessThan(3U, 2));
511 assert(!lessThan(0, 0));
512 assert(!lessThan(0U, 0));
513 assert(!lessThan(0, 0U));
514 }
515
516 /**
517 Predicate that returns $(D_PARAM a > b).
518 Correctly compares signed and unsigned integers, ie. 2U > -1.
519 */
520 alias greaterThan = safeOp!">";
521
522 ///
523 @safe unittest
524 {
525 assert(!greaterThan(2, 3));
526 assert(!greaterThan(2U, 3U));
527 assert(!greaterThan(2, 3.0));
528 assert(!greaterThan(-2, 3U));
529 assert(!greaterThan(2, 3U));
530 assert(greaterThan(3U, -2));
531 assert(greaterThan(3U, 2));
532 assert(!greaterThan(0, 0));
533 assert(!greaterThan(0U, 0));
534 assert(!greaterThan(0, 0U));
535 }
536
537 /**
538 Predicate that returns $(D_PARAM a == b).
539 Correctly compares signed and unsigned integers, ie. !(-1 == ~0U).
540 */
541 alias equalTo = safeOp!"==";
542
543 ///
544 @safe unittest
545 {
546 assert(equalTo(0U, 0));
547 assert(equalTo(0, 0U));
548 assert(!equalTo(-1, ~0U));
549 }
550 /**
551 N-ary predicate that reverses the order of arguments, e.g., given
552 $(D pred(a, b, c)), returns $(D pred(c, b, a)).
553
554 Params:
555 pred = A callable
556 Returns:
557 A function which calls `pred` after reversing the given parameters
558 */
reverseArgs(alias pred)559 template reverseArgs(alias pred)
560 {
561 auto reverseArgs(Args...)(auto ref Args args)
562 if (is(typeof(pred(Reverse!args))))
563 {
564 return pred(Reverse!args);
565 }
566 }
567
568 ///
569 @safe unittest
570 {
571 alias gt = reverseArgs!(binaryFun!("a < b"));
572 assert(gt(2, 1) && !gt(1, 1));
573 }
574
575 ///
576 @safe unittest
577 {
578 int x = 42;
xyz(int a,int b)579 bool xyz(int a, int b) { return a * x < b / x; }
580 auto foo = &xyz;
581 foo(4, 5);
582 alias zyx = reverseArgs!(foo);
583 assert(zyx(5, 4) == foo(4, 5));
584 }
585
586 ///
587 @safe unittest
588 {
589 alias gt = reverseArgs!(binaryFun!("a < b"));
590 assert(gt(2, 1) && !gt(1, 1));
591 int x = 42;
xyz(int a,int b)592 bool xyz(int a, int b) { return a * x < b / x; }
593 auto foo = &xyz;
594 foo(4, 5);
595 alias zyx = reverseArgs!(foo);
596 assert(zyx(5, 4) == foo(4, 5));
597 }
598
599 ///
600 @safe unittest
601 {
abc(int a,int b,int c)602 int abc(int a, int b, int c) { return a * b + c; }
603 alias cba = reverseArgs!abc;
604 assert(abc(91, 17, 32) == cba(32, 17, 91));
605 }
606
607 ///
608 @safe unittest
609 {
a(int a)610 int a(int a) { return a * 2; }
611 alias _a = reverseArgs!a;
612 assert(a(2) == _a(2));
613 }
614
615 ///
616 @safe unittest
617 {
b()618 int b() { return 4; }
619 alias _b = reverseArgs!b;
620 assert(b() == _b());
621 }
622
623 /**
624 Negates predicate `pred`.
625
626 Params:
627 pred = A string or a callable
628 Returns:
629 A function which calls `pred` and returns the logical negation of its
630 return value.
631 */
not(alias pred)632 template not(alias pred)
633 {
634 auto not(T...)(auto ref T args)
635 {
636 static if (is(typeof(!pred(args))))
637 return !pred(args);
638 else static if (T.length == 1)
639 return !unaryFun!pred(args);
640 else static if (T.length == 2)
641 return !binaryFun!pred(args);
642 else
643 static assert(0);
644 }
645 }
646
647 ///
648 @safe unittest
649 {
650 import std.algorithm.searching : find;
651 import std.uni : isWhite;
652 string a = " Hello, world!";
653 assert(find!(not!isWhite)(a) == "Hello, world!");
654 }
655
656 @safe unittest
657 {
658 assert(not!"a != 5"(5));
659 assert(not!"a != b"(5, 5));
660
661 assert(not!(() => false)());
662 assert(not!(a => a != 5)(5));
663 assert(not!((a, b) => a != b)(5, 5));
664 assert(not!((a, b, c) => a * b * c != 125 )(5, 5, 5));
665 }
666
667 /**
668 $(LINK2 http://en.wikipedia.org/wiki/Partial_application, Partially
669 applies) $(D_PARAM fun) by tying its first argument to $(D_PARAM arg).
670
671 Params:
672 fun = A callable
673 arg = The first argument to apply to `fun`
674 Returns:
675 A new function which calls `fun` with `arg` plus the passed parameters.
676 */
partial(alias fun,alias arg)677 template partial(alias fun, alias arg)
678 {
679 import std.traits : isCallable;
680 // Check whether fun is a user defined type which implements opCall or a template.
681 // As opCall itself can be templated, std.traits.isCallable does not work here.
682 enum isSomeFunctor = (is(typeof(fun) == struct) || is(typeof(fun) == class)) && __traits(hasMember, fun, "opCall");
683 static if (isSomeFunctor || __traits(isTemplate, fun))
684 {
685 auto partial(Ts...)(Ts args2)
686 {
687 static if (is(typeof(fun(arg, args2))))
688 {
689 return fun(arg, args2);
690 }
691 else
692 {
693 static string errormsg()
694 {
695 string msg = "Cannot call '" ~ fun.stringof ~ "' with arguments " ~
696 "(" ~ arg.stringof;
697 foreach (T; Ts)
698 msg ~= ", " ~ T.stringof;
699 msg ~= ").";
700 return msg;
701 }
702 static assert(0, errormsg());
703 }
704 }
705 }
706 else static if (!isCallable!fun)
707 {
708 static assert(false, "Cannot apply partial to a non-callable '" ~ fun.stringof ~ "'.");
709 }
710 else // Assume fun is callable and uniquely defined.
711 {
712 static if (Parameters!fun.length == 0)
713 {
714 static assert(0, "Cannot partially apply '" ~ fun.stringof ~ "'." ~
715 "'" ~ fun.stringof ~ "' has 0 arguments.");
716 }
717 else static if (!is(typeof(arg) : Parameters!fun[0]))
718 {
719 string errorMsg()
720 {
721 string msg = "Argument mismatch for '" ~ fun.stringof ~ "': expected " ~
722 Parameters!fun[0].stringof ~ ", but got " ~ typeof(arg).stringof ~ ".";
723 return msg;
724 }
725 static assert(0, errorMsg());
726 }
727 else
728 {
729 import std.traits : ReturnType;
730 ReturnType!fun partial(Parameters!fun[1..$] args2)
731 {
732 return fun(arg, args2);
733 }
734 }
735 }
736 }
737
738 ///
739 @safe unittest
740 {
fun(int a,int b)741 int fun(int a, int b) { return a + b; }
742 alias fun5 = partial!(fun, 5);
743 assert(fun5(6) == 11);
744 // Note that in most cases you'd use an alias instead of a value
745 // assignment. Using an alias allows you to partially evaluate template
746 // functions without committing to a particular type of the function.
747 }
748
749 // tests for partially evaluating callables
750 @safe unittest
751 {
f1(int a,int b)752 static int f1(int a, int b) { return a + b; }
753 assert(partial!(f1, 5)(6) == 11);
754
f2(int a,int b)755 int f2(int a, int b) { return a + b; }
756 int x = 5;
757 assert(partial!(f2, x)(6) == 11);
758 x = 7;
759 assert(partial!(f2, x)(6) == 13);
760 static assert(partial!(f2, 5)(6) == 11);
761
762 auto dg = &f2;
763 auto f3 = &partial!(dg, x);
764 assert(f3(6) == 13);
765
funOneArg(int a)766 static int funOneArg(int a) { return a; }
767 assert(partial!(funOneArg, 1)() == 1);
768
funThreeArgs(int a,int b,int c)769 static int funThreeArgs(int a, int b, int c) { return a + b + c; }
770 alias funThreeArgs1 = partial!(funThreeArgs, 1);
771 assert(funThreeArgs1(2, 3) == 6);
772 static assert(!is(typeof(funThreeArgs1(2))));
773
774 enum xe = 5;
775 alias fe = partial!(f2, xe);
776 static assert(fe(6) == 11);
777 }
778
779 // tests for partially evaluating templated/overloaded callables
780 @safe unittest
781 {
add(A,B)782 static auto add(A, B)(A x, B y)
783 {
784 return x + y;
785 }
786
787 alias add5 = partial!(add, 5);
788 assert(add5(6) == 11);
789 static assert(!is(typeof(add5())));
790 static assert(!is(typeof(add5(6, 7))));
791
792 // taking address of templated partial evaluation needs explicit type
793 auto dg = &add5!(int);
794 assert(dg(6) == 11);
795
796 int x = 5;
797 alias addX = partial!(add, x);
798 assert(addX(6) == 11);
799
800 static struct Callable
801 {
opCallCallable802 static string opCall(string a, string b) { return a ~ b; }
opCallCallable803 int opCall(int a, int b) { return a * b; }
opCallCallable804 double opCall(double a, double b) { return a + b; }
805 }
806 Callable callable;
807 assert(partial!(Callable, "5")("6") == "56");
808 assert(partial!(callable, 5)(6) == 30);
809 assert(partial!(callable, 7.0)(3.0) == 7.0 + 3.0);
810
811 static struct TCallable
812 {
opCallTCallable813 auto opCall(A, B)(A a, B b)
814 {
815 return a + b;
816 }
817 }
818 TCallable tcallable;
819 assert(partial!(tcallable, 5)(6) == 11);
820 static assert(!is(typeof(partial!(tcallable, "5")(6))));
821
822 static struct NonCallable{}
823 static assert(!__traits(compiles, partial!(NonCallable, 5)), "Partial should not work on non-callable structs.");
824 static assert(!__traits(compiles, partial!(NonCallable.init, 5)),
825 "Partial should not work on instances of non-callable structs.");
826
funOneArg(A)827 static A funOneArg(A)(A a) { return a; }
828 alias funOneArg1 = partial!(funOneArg, 1);
829 assert(funOneArg1() == 1);
830
funThreeArgs(A,B,C)831 static auto funThreeArgs(A, B, C)(A a, B b, C c) { return a + b + c; }
832 alias funThreeArgs1 = partial!(funThreeArgs, 1);
833 assert(funThreeArgs1(2, 3) == 6);
834 static assert(!is(typeof(funThreeArgs1(1))));
835
836 auto dg2 = &funOneArg1!();
837 assert(dg2() == 1);
838 }
839
840 // Fix https://issues.dlang.org/show_bug.cgi?id=15732
841 @safe unittest
842 {
843 // Test whether it works with functions.
partialFunction()844 auto partialFunction(){
845 auto fullFunction = (float a, float b, float c) => a + b / c;
846 alias apply1 = partial!(fullFunction, 1);
847 return &apply1;
848 }
849 auto result = partialFunction()(2, 4);
850 assert(result == 1.5f);
851
852 // And with delegates.
partialDelegate(float c)853 auto partialDelegate(float c){
854 auto fullDelegate = (float a, float b) => a + b / c;
855 alias apply1 = partial!(fullDelegate, 1);
856 return &apply1;
857 }
858 auto result2 = partialDelegate(4)(2);
859 assert(result2 == 1.5f);
860 }
861
862 /**
863 Takes a function of (potentially) many arguments, and returns a function taking
864 one argument and returns a callable taking the rest. f(x, y) == curry(f)(x)(y)
865
866 Params:
867 F = a function taking at least one argument
868 t = a callable object whose opCall takes at least 1 object
869 Returns:
870 A single parameter callable object
871 */
872 template curry(alias F)
873 if (isCallable!F && Parameters!F.length)
874 {
875 //inspired from the implementation from Artur Skawina here:
876 //https://forum.dlang.org/post/mailman.1626.1340110492.24740.digitalmars-d@puremagic.com
877 //This implementation stores a copy of all filled in arguments with each curried result
878 //this way, the curried functions are independent and don't share any references
879 //eg: auto fc = curry!f; auto fc1 = fc(1); auto fc2 = fc(2); fc1(3) != fc2(3)
CurryImpl(size_t N)880 struct CurryImpl(size_t N)
881 {
882 alias FParams = Parameters!F;
883 FParams[0 .. N] storedArguments;
884 static if (N > 0)
885 {
886 this(U : FParams[N - 1])(ref CurryImpl!(N - 1) prev, ref U arg)
887 {
888 storedArguments[0 .. N - 1] = prev.storedArguments[];
889 storedArguments[N-1] = arg;
890 }
891 }
892
893 auto opCall(U : FParams[N])(auto ref U arg) return scope
894 {
895 static if (N == FParams.length - 1)
896 {
897 return F(storedArguments, arg);
898 }
899 else
900 {
901 return CurryImpl!(N + 1)(this, arg);
902 }
903 }
904 }
905
906 auto curry()
907 {
908 CurryImpl!0 res;
909 return res; // return CurryImpl!0.init segfaults for delegates on Windows
910 }
911 }
912
913 ///
914 pure @safe @nogc nothrow unittest
915 {
916 int f(int x, int y, int z)
917 {
918 return x + y + z;
919 }
920 auto cf = curry!f;
921 auto cf1 = cf(1);
922 auto cf2 = cf(2);
923
924 assert(cf1(2)(3) == f(1, 2, 3));
925 assert(cf2(2)(3) == f(2, 2, 3));
926 }
927
928 ///ditto
929 auto curry(T)(T t)
930 if (isCallable!T && Parameters!T.length)
931 {
932 static auto fun(ref T inst, ref Parameters!T args)
933 {
934 return inst(args);
935 }
936
937 return curry!fun()(t);
938 }
939
940 ///
941 pure @safe @nogc nothrow unittest
942 {
943 //works with callable structs too
944 struct S
945 {
946 int w;
947 int opCall(int x, int y, int z)
948 {
949 return w + x + y + z;
950 }
951 }
952
953 S s;
954 s.w = 5;
955
956 auto cs = curry(s);
957 auto cs1 = cs(1);
958 auto cs2 = cs(2);
959
960 assert(cs1(2)(3) == s(1, 2, 3));
961 assert(cs1(2)(3) == (1 + 2 + 3 + 5));
962 assert(cs2(2)(3) ==s(2, 2, 3));
963 }
964
965
966 @safe pure @nogc nothrow unittest
967 {
968 //currying a single argument function does nothing
969 int pork(int a){ return a*2;}
970 auto curryPork = curry!pork;
971 assert(curryPork(0) == pork(0));
972 assert(curryPork(1) == pork(1));
973 assert(curryPork(-1) == pork(-1));
974 assert(curryPork(1000) == pork(1000));
975
976 //test 2 argument function
977 double mixedVeggies(double a, int b, bool)
978 {
979 return a + b;
980 }
981
982 auto mixedCurry = curry!mixedVeggies;
983 assert(mixedCurry(10)(20)(false) == mixedVeggies(10, 20, false));
984 assert(mixedCurry(100)(200)(true) == mixedVeggies(100, 200, true));
985
986 // struct with opCall
987 struct S
988 {
989 double opCall(int x, double y, short z) const pure nothrow @nogc
990 {
991 return x*y*z;
992 }
993 }
994
995 S s;
996 auto curriedStruct = curry(s);
997 assert(curriedStruct(1)(2)(short(3)) == s(1, 2, short(3)));
998 assert(curriedStruct(300)(20)(short(10)) == s(300, 20, short(10)));
999 }
1000
1001 pure @safe nothrow unittest
1002 {
1003 auto cfl = curry!((double a, int b) => a + b);
1004 assert(cfl(13)(2) == 15);
1005
1006 int c = 42;
1007 auto cdg = curry!((double a, int b) => a + b + c);
1008 assert(cdg(13)(2) == 57);
1009
1010 static class C
1011 {
1012 int opCall(int mult, int add) pure @safe nothrow @nogc scope
1013 {
1014 return mult * 42 + add;
1015 }
1016 }
1017
1018 scope C ci = new C();
1019 scope cc = curry(ci);
1020 assert(cc(2)(4) == ci(2, 4));
1021 }
1022
1023 // Disallows callables without parameters
1024 pure @safe @nogc nothrow unittest
1025 {
1026 static void noargs() {}
1027 static assert(!__traits(compiles, curry!noargs()));
1028
1029 static struct NoArgs
1030 {
1031 void opCall() {}
1032 }
1033
1034 static assert(!__traits(compiles, curry(NoArgs.init)));
1035 }
1036
1037 private template Iota(size_t n)
1038 {
1039 static if (n == 0)
1040 alias Iota = AliasSeq!();
1041 else
1042 alias Iota = AliasSeq!(Iota!(n - 1), n - 1);
1043 }
1044
1045 /**
1046 Takes multiple functions and adjoins them together.
1047
1048 Params:
1049 F = the call-able(s) to adjoin
1050 Returns:
1051 A new function which returns a $(REF Tuple, std,typecons). Each of the
1052 elements of the tuple will be the return values of `F`.
1053
1054 Note: In the special case where only a single function is provided
1055 ($(D F.length == 1)), adjoin simply aliases to the single passed function
1056 (`F[0]`).
1057 */
1058 template adjoin(F...)
1059 if (F.length == 1)
1060 {
1061 alias adjoin = F[0];
1062 }
1063 /// ditto
1064 template adjoin(F...)
1065 if (F.length > 1)
1066 {
1067 auto adjoin(V...)(auto ref V a)
1068 {
1069 import std.typecons : tuple;
1070 import std.meta : staticMap;
1071
1072 auto resultElement(size_t i)()
1073 {
1074 return F[i](a);
1075 }
1076
1077 return tuple(staticMap!(resultElement, Iota!(F.length)));
1078 }
1079 }
1080
1081 ///
1082 @safe unittest
1083 {
1084 import std.typecons : Tuple;
1085 static bool f1(int a) { return a != 0; }
1086 static int f2(int a) { return a / 2; }
1087 auto x = adjoin!(f1, f2)(5);
1088 assert(is(typeof(x) == Tuple!(bool, int)));
1089 assert(x[0] == true && x[1] == 2);
1090 }
1091
1092 @safe unittest
1093 {
1094 import std.typecons : Tuple;
1095 static bool F1(int a) { return a != 0; }
1096 auto x1 = adjoin!(F1)(5);
1097 static int F2(int a) { return a / 2; }
1098 auto x2 = adjoin!(F1, F2)(5);
1099 assert(is(typeof(x2) == Tuple!(bool, int)));
1100 assert(x2[0] && x2[1] == 2);
1101 auto x3 = adjoin!(F1, F2, F2)(5);
1102 assert(is(typeof(x3) == Tuple!(bool, int, int)));
1103 assert(x3[0] && x3[1] == 2 && x3[2] == 2);
1104
1105 bool F4(int a) { return a != x1; }
1106 alias eff4 = adjoin!(F4);
1107 static struct S
1108 {
1109 bool delegate(int) @safe store;
1110 int fun() { return 42 + store(5); }
1111 }
1112 S s;
1113 s.store = (int a) { return eff4(a); };
1114 auto x4 = s.fun();
1115 assert(x4 == 43);
1116 }
1117
1118 @safe unittest
1119 {
1120 import std.meta : staticMap;
1121 import std.typecons : Tuple, tuple;
1122 alias funs = staticMap!(unaryFun, "a", "a * 2", "a * 3", "a * a", "-a");
1123 alias afun = adjoin!funs;
1124 assert(afun(5) == tuple(5, 10, 15, 25, -5));
1125
1126 static class C{}
1127 alias IC = immutable(C);
1128 IC foo(){return typeof(return).init;}
1129 Tuple!(IC, IC, IC, IC) ret1 = adjoin!(foo, foo, foo, foo)();
1130
1131 static struct S{int* p;}
1132 alias IS = immutable(S);
1133 IS bar(){return typeof(return).init;}
1134 enum Tuple!(IS, IS, IS, IS) ret2 = adjoin!(bar, bar, bar, bar)();
1135 }
1136
1137 // https://issues.dlang.org/show_bug.cgi?id=21347
1138 @safe @betterC unittest
1139 {
1140 alias f = (int n) => n + 1;
1141 alias g = (int n) => n + 2;
1142 alias h = (int n) => n + 3;
1143 alias i = (int n) => n + 4;
1144
1145 auto result = adjoin!(f, g, h, i)(0);
1146
1147 assert(result[0] == 1);
1148 assert(result[1] == 2);
1149 assert(result[2] == 3);
1150 assert(result[3] == 4);
1151 }
1152
1153 /**
1154 Composes passed-in functions $(D fun[0], fun[1], ...).
1155
1156 Params:
1157 fun = the call-able(s) or `string`(s) to compose into one function
1158 Returns:
1159 A new function `f(x)` that in turn returns `fun[0](fun[1](...(x)))...`.
1160
1161 See_Also: $(LREF pipe)
1162 */
1163 template compose(fun...)
1164 if (fun.length > 0)
1165 {
1166 static if (fun.length == 1)
1167 {
1168 alias compose = unaryFun!(fun[0]);
1169 }
1170 else
1171 {
1172 alias fun0 = unaryFun!(fun[0]);
1173 alias rest = compose!(fun[1 .. $]);
1174
1175 auto compose(Args...)(Args args)
1176 {
1177 return fun0(rest(args));
1178 }
1179 }
1180 }
1181
1182 ///
1183 @safe unittest
1184 {
1185 import std.algorithm.comparison : equal;
1186 import std.algorithm.iteration : map;
1187 import std.array : split;
1188 import std.conv : to;
1189
1190 // First split a string in whitespace-separated tokens and then
1191 // convert each token into an integer
1192 assert(compose!(map!(to!(int)), split)("1 2 3").equal([1, 2, 3]));
1193 }
1194
1195 // https://issues.dlang.org/show_bug.cgi?id=6484
1196 @safe unittest
1197 {
1198 int f(int a) { return a; }
1199 int g(int a) { return a; }
1200 int h(int a,int b,int c) { return a * b * c; }
1201
1202 alias F = compose!(f,g,h);
1203 assert(F(1,2,3) == f(g(h(1,2,3))));
1204 }
1205
1206 /**
1207 Pipes functions in sequence. Offers the same functionality as $(D
1208 compose), but with functions specified in reverse order. This may
1209 lead to more readable code in some situation because the order of
1210 execution is the same as lexical order.
1211
1212 Params:
1213 fun = the call-able(s) or `string`(s) to compose into one function
1214 Returns:
1215 A new function `f(x)` that in turn returns `fun[$-1](...fun[1](fun[0](x)))...`.
1216
1217 Example:
1218
1219 ----
1220 // Read an entire text file, split the resulting string in
1221 // whitespace-separated tokens, and then convert each token into an
1222 // integer
1223 int[] a = pipe!(readText, split, map!(to!(int)))("file.txt");
1224 ----
1225
1226 See_Also: $(LREF compose)
1227 */
1228 alias pipe(fun...) = compose!(Reverse!(fun));
1229
1230 ///
1231 @safe unittest
1232 {
1233 import std.conv : to;
1234 string foo(int a) { return to!(string)(a); }
1235 int bar(string a) { return to!(int)(a) + 1; }
1236 double baz(int a) { return a + 0.5; }
1237 assert(compose!(baz, bar, foo)(1) == 2.5);
1238 assert(pipe!(foo, bar, baz)(1) == 2.5);
1239
1240 assert(compose!(baz, `to!(int)(a) + 1`, foo)(1) == 2.5);
1241 assert(compose!(baz, bar)("1"[]) == 2.5);
1242
1243 assert(compose!(baz, bar)("1") == 2.5);
1244
1245 assert(compose!(`a + 0.5`, `to!(int)(a) + 1`, foo)(1) == 2.5);
1246 }
1247
1248 /**
1249 * $(LINK2 https://en.wikipedia.org/wiki/Memoization, Memoizes) a function so as
1250 * to avoid repeated computation. The memoization structure is a hash table keyed by a
1251 * tuple of the function's arguments. There is a speed gain if the
1252 * function is repeatedly called with the same arguments and is more
1253 * expensive than a hash table lookup. For more information on memoization, refer to $(HTTP docs.google.com/viewer?url=http%3A%2F%2Fhop.perl.plover.com%2Fbook%2Fpdf%2F03CachingAndMemoization.pdf, this book chapter).
1254
1255 Example:
1256 ----
1257 double transmogrify(int a, string b)
1258 {
1259 ... expensive computation ...
1260 }
1261 alias fastTransmogrify = memoize!transmogrify;
1262 unittest
1263 {
1264 auto slow = transmogrify(2, "hello");
1265 auto fast = fastTransmogrify(2, "hello");
1266 assert(slow == fast);
1267 }
1268 ----
1269
1270 Params:
1271 fun = the call-able to memozie
1272 maxSize = The maximum size of the GC buffer to hold the return values
1273 Returns:
1274 A new function which calls `fun` and caches its return values.
1275
1276 Note:
1277 Technically the memoized function should be pure because `memoize` assumes it will
1278 always return the same result for a given tuple of arguments. However, `memoize` does not
1279 enforce that because sometimes it is useful to memoize an impure function, too.
1280 */
1281 template memoize(alias fun)
1282 {
1283 import std.traits : ReturnType;
1284 // https://issues.dlang.org/show_bug.cgi?id=13580
1285 // alias Args = Parameters!fun;
1286
1287 ReturnType!fun memoize(Parameters!fun args)
1288 {
1289 alias Args = Parameters!fun;
1290 import std.typecons : Tuple;
1291 import std.traits : Unqual;
1292
1293 static Unqual!(ReturnType!fun)[Tuple!Args] memo;
1294 auto t = Tuple!Args(args);
1295 if (auto p = t in memo)
1296 return *p;
1297 auto r = fun(args);
1298 memo[t] = r;
1299 return r;
1300 }
1301 }
1302
1303 /// ditto
1304 template memoize(alias fun, uint maxSize)
1305 {
1306 import std.traits : ReturnType;
1307 // https://issues.dlang.org/show_bug.cgi?id=13580
1308 // alias Args = Parameters!fun;
1309 ReturnType!fun memoize(Parameters!fun args)
1310 {
1311 import std.meta : staticMap;
1312 import std.traits : hasIndirections, Unqual;
1313 import std.typecons : tuple;
1314 static struct Value { staticMap!(Unqual, Parameters!fun) args; Unqual!(ReturnType!fun) res; }
1315 static Value[] memo;
1316 static size_t[] initialized;
1317
1318 if (!memo.length)
1319 {
1320 import core.memory : GC;
1321
1322 // Ensure no allocation overflows
1323 static assert(maxSize < size_t.max / Value.sizeof);
1324 static assert(maxSize < size_t.max - (8 * size_t.sizeof - 1));
1325
1326 enum attr = GC.BlkAttr.NO_INTERIOR | (hasIndirections!Value ? 0 : GC.BlkAttr.NO_SCAN);
1327 memo = (cast(Value*) GC.malloc(Value.sizeof * maxSize, attr))[0 .. maxSize];
1328 enum nwords = (maxSize + 8 * size_t.sizeof - 1) / (8 * size_t.sizeof);
1329 initialized = (cast(size_t*) GC.calloc(nwords * size_t.sizeof, attr | GC.BlkAttr.NO_SCAN))[0 .. nwords];
1330 }
1331
1332 import core.bitop : bt, bts;
1333 import core.lifetime : emplace;
1334
1335 size_t hash;
1336 foreach (ref arg; args)
1337 hash = hashOf(arg, hash);
1338 // cuckoo hashing
1339 immutable idx1 = hash % maxSize;
1340 if (!bt(initialized.ptr, idx1))
1341 {
1342 emplace(&memo[idx1], args, fun(args));
1343 // only set to initialized after setting args and value
1344 // https://issues.dlang.org/show_bug.cgi?id=14025
1345 bts(initialized.ptr, idx1);
1346 return memo[idx1].res;
1347 }
1348 else if (memo[idx1].args == args)
1349 return memo[idx1].res;
1350 // FNV prime
1351 immutable idx2 = (hash * 16_777_619) % maxSize;
1352 if (!bt(initialized.ptr, idx2))
1353 {
1354 emplace(&memo[idx2], memo[idx1]);
1355 bts(initialized.ptr, idx2);
1356 }
1357 else if (memo[idx2].args == args)
1358 return memo[idx2].res;
1359 else if (idx1 != idx2)
1360 memo[idx2] = memo[idx1];
1361
1362 memo[idx1] = Value(args, fun(args));
1363 return memo[idx1].res;
1364 }
1365 }
1366
1367 /**
1368 * To _memoize a recursive function, simply insert the memoized call in lieu of the plain recursive call.
1369 * For example, to transform the exponential-time Fibonacci implementation into a linear-time computation:
1370 */
1371 @safe nothrow
1372 unittest
1373 {
1374 ulong fib(ulong n) @safe nothrow
1375 {
1376 return n < 2 ? n : memoize!fib(n - 2) + memoize!fib(n - 1);
1377 }
1378 assert(fib(10) == 55);
1379 }
1380
1381 /**
1382 * To improve the speed of the factorial function,
1383 */
1384 @safe unittest
1385 {
1386 ulong fact(ulong n) @safe
1387 {
1388 return n < 2 ? 1 : n * memoize!fact(n - 1);
1389 }
1390 assert(fact(10) == 3628800);
1391 }
1392
1393 /**
1394 * This memoizes all values of `fact` up to the largest argument. To only cache the final
1395 * result, move `memoize` outside the function as shown below.
1396 */
1397 @safe unittest
1398 {
1399 ulong factImpl(ulong n) @safe
1400 {
1401 return n < 2 ? 1 : n * factImpl(n - 1);
1402 }
1403 alias fact = memoize!factImpl;
1404 assert(fact(10) == 3628800);
1405 }
1406
1407 /**
1408 * When the `maxSize` parameter is specified, memoize will used
1409 * a fixed size hash table to limit the number of cached entries.
1410 */
1411 @system unittest // not @safe due to memoize
1412 {
1413 ulong fact(ulong n)
1414 {
1415 // Memoize no more than 8 values
1416 return n < 2 ? 1 : n * memoize!(fact, 8)(n - 1);
1417 }
1418 assert(fact(8) == 40320);
1419 // using more entries than maxSize will overwrite existing entries
1420 assert(fact(10) == 3628800);
1421 }
1422
1423 @system unittest // not @safe due to memoize
1424 {
1425 import core.math : sqrt;
1426 alias msqrt = memoize!(function double(double x) { return sqrt(x); });
1427 auto y = msqrt(2.0);
1428 assert(y == msqrt(2.0));
1429 y = msqrt(4.0);
1430 assert(y == sqrt(4.0));
1431
1432 // alias mrgb2cmyk = memoize!rgb2cmyk;
1433 // auto z = mrgb2cmyk([43, 56, 76]);
1434 // assert(z == mrgb2cmyk([43, 56, 76]));
1435
1436 //alias mfib = memoize!fib;
1437
1438 static ulong fib(ulong n) @safe
1439 {
1440 alias mfib = memoize!fib;
1441 return n < 2 ? 1 : mfib(n - 2) + mfib(n - 1);
1442 }
1443
1444 auto z = fib(10);
1445 assert(z == 89);
1446
1447 static ulong fact(ulong n) @safe
1448 {
1449 alias mfact = memoize!fact;
1450 return n < 2 ? 1 : n * mfact(n - 1);
1451 }
1452 assert(fact(10) == 3628800);
1453
1454 // https://issues.dlang.org/show_bug.cgi?id=12568
1455 static uint len2(const string s) { // Error
1456 alias mLen2 = memoize!len2;
1457 if (s.length == 0)
1458 return 0;
1459 else
1460 return 1 + mLen2(s[1 .. $]);
1461 }
1462
1463 int _func(int x) @safe { return 1; }
1464 alias func = memoize!(_func, 10);
1465 assert(func(int.init) == 1);
1466 assert(func(int.init) == 1);
1467 }
1468
1469 // https://issues.dlang.org/show_bug.cgi?id=16079
1470 // memoize should work with arrays
1471 @system unittest // not @safe with -dip1000 due to memoize
1472 {
1473 int executed = 0;
1474 T median(T)(const T[] nums) {
1475 import std.algorithm.sorting : sort;
1476 executed++;
1477 auto arr = nums.dup;
1478 arr.sort();
1479 if (arr.length % 2)
1480 return arr[$ / 2];
1481 else
1482 return (arr[$ / 2 - 1]
1483 + arr[$ / 2]) / 2;
1484 }
1485
1486 alias fastMedian = memoize!(median!int);
1487
1488 assert(fastMedian([7, 5, 3]) == 5);
1489 assert(fastMedian([7, 5, 3]) == 5);
1490
1491 assert(executed == 1);
1492 }
1493
1494 // https://issues.dlang.org/show_bug.cgi?id=16079: memoize should work with structs
1495 @safe unittest
1496 {
1497 int executed = 0;
1498 T pickFirst(T)(T first)
1499 {
1500 executed++;
1501 return first;
1502 }
1503
1504 struct Foo { int k; }
1505 Foo A = Foo(3);
1506
1507 alias first = memoize!(pickFirst!Foo);
1508 assert(first(Foo(3)) == A);
1509 assert(first(Foo(3)) == A);
1510 assert(executed == 1);
1511 }
1512
1513 // https://issues.dlang.org/show_bug.cgi?id=20439 memoize should work with void opAssign
1514 @safe unittest
1515 {
1516 static struct S
1517 {
1518 void opAssign(S) {}
1519 }
1520
1521 assert(memoize!(() => S()) == S());
1522 }
1523
1524 // https://issues.dlang.org/show_bug.cgi?id=16079: memoize should work with classes
1525 @system unittest // not @safe with -dip1000 due to memoize
1526 {
1527 int executed = 0;
1528 T pickFirst(T)(T first)
1529 {
1530 executed++;
1531 return first;
1532 }
1533
1534 class Bar
1535 {
1536 size_t k;
1537 this(size_t k)
1538 {
1539 this.k = k;
1540 }
1541 override size_t toHash()
1542 {
1543 return k;
1544 }
1545 override bool opEquals(Object o)
1546 {
1547 auto b = cast(Bar) o;
1548 return b && k == b.k;
1549 }
1550 }
1551
1552 alias firstClass = memoize!(pickFirst!Bar);
1553 assert(firstClass(new Bar(3)).k == 3);
1554 assert(firstClass(new Bar(3)).k == 3);
1555 assert(executed == 1);
1556 }
1557
1558 // https://issues.dlang.org/show_bug.cgi?id=20302
1559 @system unittest
1560 {
1561 version (none) // TODO change `none` to `all` and fix remaining limitations
1562 struct S { const int len; }
1563 else
1564 struct S { int len; }
1565
1566 static string fun000( string str, S s) { return str[0 .. s.len] ~ "123"; }
1567 static string fun001( string str, const S s) { return str[0 .. s.len] ~ "123"; }
1568 static string fun010(const string str, S s) { return str[0 .. s.len] ~ "123"; }
1569 static string fun011(const string str, const S s) { return str[0 .. s.len] ~ "123"; }
1570 static const(string) fun100( string str, S s) { return str[0 .. s.len] ~ "123"; }
1571 static const(string) fun101( string str, const S s) { return str[0 .. s.len] ~ "123"; }
1572 static const(string) fun110(const string str, S s) { return str[0 .. s.len] ~ "123"; }
1573 static const(string) fun111(const string str, const S s) { return str[0 .. s.len] ~ "123"; }
1574
1575 static foreach (fun; AliasSeq!(fun000, fun001, fun010, fun011, fun100, fun101, fun110, fun111))
1576 {{
1577 alias mfun = memoize!fun;
1578 assert(mfun("abcdefgh", S(3)) == "abc123");
1579
1580 alias mfun2 = memoize!(fun, 42);
1581 assert(mfun2("asd", S(3)) == "asd123");
1582 }}
1583 }
1584
1585 private struct DelegateFaker(F)
1586 {
1587 import std.typecons : FuncInfo, MemberFunctionGenerator;
1588
1589 // for @safe
1590 static F castToF(THIS)(THIS x) @trusted
1591 {
1592 return cast(F) x;
1593 }
1594
1595 /*
1596 * What all the stuff below does is this:
1597 *--------------------
1598 * struct DelegateFaker(F) {
1599 * extern(linkage)
1600 * [ref] ReturnType!F doIt(Parameters!F args) [@attributes]
1601 * {
1602 * auto fp = cast(F) &this;
1603 * return fp(args);
1604 * }
1605 * }
1606 *--------------------
1607 */
1608
1609 // We will use MemberFunctionGenerator in std.typecons. This is a policy
1610 // configuration for generating the doIt().
1611 template GeneratingPolicy()
1612 {
1613 // Inform the genereator that we only have type information.
1614 enum WITHOUT_SYMBOL = true;
1615
1616 // Generate the function body of doIt().
1617 template generateFunctionBody(unused...)
1618 {
1619 enum generateFunctionBody =
1620 // [ref] ReturnType doIt(Parameters args) @attributes
1621 q{
1622 // When this function gets called, the this pointer isn't
1623 // really a this pointer (no instance even really exists), but
1624 // a function pointer that points to the function to be called.
1625 // Cast it to the correct type and call it.
1626
1627 auto fp = castToF(&this);
1628 return fp(args);
1629 };
1630 }
1631 }
1632 // Type information used by the generated code.
1633 alias FuncInfo_doIt = FuncInfo!(F);
1634
1635 // Generate the member function doIt().
1636 mixin( MemberFunctionGenerator!(GeneratingPolicy!())
1637 .generateFunction!("FuncInfo_doIt", "doIt", F) );
1638 }
1639
1640 /**
1641 * Convert a callable to a delegate with the same parameter list and
1642 * return type, avoiding heap allocations and use of auxiliary storage.
1643 *
1644 * Params:
1645 * fp = a function pointer or an aggregate type with `opCall` defined.
1646 * Returns:
1647 * A delegate with the context pointer pointing to nothing.
1648 *
1649 * Example:
1650 * ----
1651 * void doStuff() {
1652 * writeln("Hello, world.");
1653 * }
1654 *
1655 * void runDelegate(void delegate() myDelegate) {
1656 * myDelegate();
1657 * }
1658 *
1659 * auto delegateToPass = toDelegate(&doStuff);
1660 * runDelegate(delegateToPass); // Calls doStuff, prints "Hello, world."
1661 * ----
1662 *
1663 * BUGS:
1664 * $(UL
1665 * $(LI Does not work with `@safe` functions.)
1666 * $(LI Ignores C-style / D-style variadic arguments.)
1667 * )
1668 */
1669 auto toDelegate(F)(auto ref F fp)
1670 if (isCallable!(F))
1671 {
1672 static if (is(F == delegate))
1673 {
1674 return fp;
1675 }
1676 else static if (is(typeof(&F.opCall) == delegate)
1677 || (is(typeof(&F.opCall) V : V*) && is(V == function)))
1678 {
1679 return toDelegate(&fp.opCall);
1680 }
1681 else
1682 {
1683 alias DelType = typeof(&(new DelegateFaker!(F)).doIt);
1684
1685 static struct DelegateFields {
1686 union {
1687 DelType del;
1688 //pragma(msg, typeof(del));
1689
1690 struct {
1691 void* contextPtr;
1692 void* funcPtr;
1693 }
1694 }
1695 }
1696
1697 // fp is stored in the returned delegate's context pointer.
1698 // The returned delegate's function pointer points to
1699 // DelegateFaker.doIt.
1700 DelegateFields df;
1701
1702 df.contextPtr = cast(void*) fp;
1703
1704 DelegateFaker!(F) dummy;
1705 auto dummyDel = &dummy.doIt;
1706 df.funcPtr = dummyDel.funcptr;
1707
1708 return df.del;
1709 }
1710 }
1711
1712 ///
1713 @system unittest
1714 {
1715 static int inc(ref uint num) {
1716 num++;
1717 return 8675309;
1718 }
1719
1720 uint myNum = 0;
1721 auto incMyNumDel = toDelegate(&inc);
1722 auto returnVal = incMyNumDel(myNum);
1723 assert(myNum == 1);
1724 }
1725
1726 @system unittest // not @safe due to toDelegate
1727 {
1728 static int inc(ref uint num) {
1729 num++;
1730 return 8675309;
1731 }
1732
1733 uint myNum = 0;
1734 auto incMyNumDel = toDelegate(&inc);
1735 int delegate(ref uint) dg = incMyNumDel;
1736 auto returnVal = incMyNumDel(myNum);
1737 assert(myNum == 1);
1738
1739 interface I { int opCall(); }
1740 class C: I { int opCall() { inc(myNum); return myNum;} }
1741 auto c = new C;
1742 auto i = cast(I) c;
1743
1744 auto getvalc = toDelegate(c);
1745 assert(getvalc() == 2);
1746
1747 auto getvali = toDelegate(i);
1748 assert(getvali() == 3);
1749
1750 struct S1 { int opCall() { inc(myNum); return myNum; } }
1751 static assert(!is(typeof(&s1.opCall) == delegate));
1752 S1 s1;
1753 auto getvals1 = toDelegate(s1);
1754 assert(getvals1() == 4);
1755
1756 struct S2 { static int opCall() { return 123456; } }
1757 static assert(!is(typeof(&S2.opCall) == delegate));
1758 S2 s2;
1759 auto getvals2 =&S2.opCall;
1760 assert(getvals2() == 123456);
1761
1762 /* test for attributes */
1763 {
1764 static int refvar = 0xDeadFace;
1765
1766 static ref int func_ref() { return refvar; }
1767 static int func_pure() pure { return 1; }
1768 static int func_nothrow() nothrow { return 2; }
1769 static int func_property() @property { return 3; }
1770 static int func_safe() @safe { return 4; }
1771 static int func_trusted() @trusted { return 5; }
1772 static int func_system() @system { return 6; }
1773 static int func_pure_nothrow() pure nothrow { return 7; }
1774 static int func_pure_nothrow_safe() pure nothrow @safe { return 8; }
1775
1776 auto dg_ref = toDelegate(&func_ref);
1777 int delegate() pure dg_pure = toDelegate(&func_pure);
1778 int delegate() nothrow dg_nothrow = toDelegate(&func_nothrow);
1779 int delegate() @property dg_property = toDelegate(&func_property);
1780 int delegate() @safe dg_safe = toDelegate(&func_safe);
1781 int delegate() @trusted dg_trusted = toDelegate(&func_trusted);
1782 int delegate() @system dg_system = toDelegate(&func_system);
1783 int delegate() pure nothrow dg_pure_nothrow = toDelegate(&func_pure_nothrow);
1784 int delegate() @safe pure nothrow dg_pure_nothrow_safe = toDelegate(&func_pure_nothrow_safe);
1785
1786 //static assert(is(typeof(dg_ref) == ref int delegate())); // [BUG@DMD]
1787
1788 assert(dg_ref() == refvar);
1789 assert(dg_pure() == 1);
1790 assert(dg_nothrow() == 2);
1791 assert(dg_property() == 3);
1792 assert(dg_safe() == 4);
1793 assert(dg_trusted() == 5);
1794 assert(dg_system() == 6);
1795 assert(dg_pure_nothrow() == 7);
1796 assert(dg_pure_nothrow_safe() == 8);
1797 }
1798 /* test for linkage */
1799 {
1800 struct S
1801 {
1802 extern(C) static void xtrnC() {}
1803 extern(D) static void xtrnD() {}
1804 }
1805 auto dg_xtrnC = toDelegate(&S.xtrnC);
1806 auto dg_xtrnD = toDelegate(&S.xtrnD);
1807 static assert(! is(typeof(dg_xtrnC) == typeof(dg_xtrnD)));
1808 }
1809 }
1810
1811 // forward used to be here but was moved to druntime
1812 template forward(args...)
1813 {
1814 import core.lifetime : fun = forward;
1815 alias forward = fun!args;
1816 }
1817