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