Add D front-end, libphobos library, and D2 testsuite.

ChangeLog:

	* Makefile.def (target_modules): Add libphobos.
	(flags_to_pass): Add GDC, GDCFLAGS, GDC_FOR_TARGET and
	GDCFLAGS_FOR_TARGET.
	(dependencies): Make libphobos depend on libatomic, libbacktrace
	configure, and zlib configure.
	(language): Add language d.
	* Makefile.in: Rebuild.
	* Makefile.tpl (BUILD_EXPORTS): Add GDC and GDCFLAGS.
	(HOST_EXPORTS): Add GDC.
	(POSTSTAGE1_HOST_EXPORTS): Add GDC and GDC_FOR_BUILD.
	(BASE_TARGET_EXPORTS): Add GDC.
	(GDC_FOR_BUILD, GDC, GDCFLAGS): New variables.
	(GDC_FOR_TARGET, GDC_FLAGS_FOR_TARGET): New variables.
	(EXTRA_HOST_FLAGS): Add GDC.
	(STAGE1_FLAGS_TO_PASS): Add GDC.
	(EXTRA_TARGET_FLAGS): Add GDC and GDCFLAGS.
	* config-ml.in: Treat GDC and GDCFLAGS like other compiler/flag
	environment variables.
	* configure: Rebuild.
	* configure.ac: Add target-libphobos to target_libraries.  Set and
	substitute GDC_FOR_BUILD and GDC_FOR_TARGET.

config/ChangeLog:

	* multi.m4: Set GDC.

gcc/ChangeLog:

	* Makefile.in (tm_d_file_list, tm_d_include_list): New variables.
	(TM_D_H, D_TARGET_DEF, D_TARGET_H, D_TARGET_OBJS): New variables.
	(tm_d.h, cs-tm_d.h, default-d.o): New rules.
	(d/d-target-hooks-def.h, s-d-target-hooks-def-h): New rules.
	(s-tm-texi): Also check timestamp on d-target.def.
	(generated_files): Add TM_D_H and d-target-hooks-def.h.
	(build/genhooks.o): Also depend on D_TARGET_DEF.
	* config.gcc (tm_d_file, d_target_objs, target_has_targetdm): New
	variables.
	* config/aarch64/aarch64-d.c: New file.
	* config/aarch64/aarch64-linux.h (GNU_USER_TARGET_D_CRITSEC_SIZE):
	Define.
	* config/aarch64/aarch64-protos.h (aarch64_d_target_versions): New
	prototype.
	* config/aarch64/aarch64.h (TARGET_D_CPU_VERSIONS): Define.
	* config/aarch64/t-aarch64 (aarch64-d.o): New rule.
	* config/arm/arm-d.c: New file.
	* config/arm/arm-protos.h (arm_d_target_versions): New prototype.
	* config/arm/arm.h (TARGET_D_CPU_VERSIONS): Define.
	* config/arm/linux-eabi.h (EXTRA_TARGET_D_OS_VERSIONS): Define.
	* config/arm/t-arm (arm-d.o): New rule.
	* config/default-d.c: New file.
	* config/glibc-d.c: New file.
	* config/gnu.h (GNU_USER_TARGET_D_OS_VERSIONS): Define.
	* config/i386/i386-d.c: New file.
	* config/i386/i386-protos.h (ix86_d_target_versions): New prototype.
	* config/i386/i386.h (TARGET_D_CPU_VERSIONS): Define.
	* config/i386/linux-common.h (EXTRA_TARGET_D_OS_VERSIONS): Define.
	(GNU_USER_TARGET_D_CRITSEC_SIZE): Define.
	* config/i386/t-i386 (i386-d.o): New rule.
	* config/kfreebsd-gnu.h (GNU_USER_TARGET_D_OS_VERSIONS): Define.
	* config/kopensolaris-gnu.h (GNU_USER_TARGET_D_OS_VERSIONS): Define.
	* config/linux-android.h (ANDROID_TARGET_D_OS_VERSIONS): Define.
	* config/linux.h (GNU_USER_TARGET_D_OS_VERSIONS): Define.
	* config/mips/linux-common.h (EXTRA_TARGET_D_OS_VERSIONS): Define.
	* config/mips/mips-d.c: New file.
	* config/mips/mips-protos.h (mips_d_target_versions): New prototype.
	* config/mips/mips.h (TARGET_D_CPU_VERSIONS): Define.
	* config/mips/t-mips (mips-d.o): New rule.
	* config/powerpcspe/linux.h (GNU_USER_TARGET_D_OS_VERSIONS): Define.
	* config/powerpcspe/linux64.h (GNU_USER_TARGET_D_OS_VERSIONS): Define.
	* config/powerpcspe/powerpcspe-d.c: New file.
	* config/powerpcspe/powerpcspe-protos.h (rs6000_d_target_versions):
	New prototype.
	* config/powerpcspe/powerpcspe.c (rs6000_output_function_epilogue):
	Support GNU D by using 0 as the language type.
	* config/powerpcspe/powerpcspe.h (TARGET_D_CPU_VERSIONS): Define.
	* config/powerpcspe/t-powerpcspe (powerpcspe-d.o): New rule.
	* config/riscv/riscv-d.c: New file.
	* config/riscv/riscv-protos.h (riscv_d_target_versions): New
	prototype.
	* config/riscv/riscv.h (TARGET_D_CPU_VERSIONS): Define.
	* config/riscv/t-riscv (riscv-d.o): New rule.
	* config/rs6000/linux.h (GNU_USER_TARGET_D_OS_VERSIONS): Define.
	* config/rs6000/linux64.h (GNU_USER_TARGET_D_OS_VERSIONS): Define.
	* config/rs6000/rs6000-d.c: New file.
	* config/rs6000/rs6000-protos.h (rs6000_d_target_versions): New
	prototype.
	* config/rs6000/rs6000.c (rs6000_output_function_epilogue):
	Support GNU D by using 0 as the language type.
	* config/rs6000/rs6000.h (TARGET_D_CPU_VERSIONS): Define.
	* config/rs6000/t-rs6000 (rs6000-d.o): New rule.
	* config/s390/s390-d.c: New file.
	* config/s390/s390-protos.h (s390_d_target_versions): New prototype.
	* config/s390/s390.h (TARGET_D_CPU_VERSIONS): Define.
	* config/s390/t-s390 (s390-d.o): New rule.
	* config/sparc/sparc-d.c: New file.
	* config/sparc/sparc-protos.h (sparc_d_target_versions): New
	prototype.
	* config/sparc/sparc.h (TARGET_D_CPU_VERSIONS): Define.
	* config/sparc/t-sparc (sparc-d.o): New rule.
	* config/t-glibc (glibc-d.o): New rule.
	* configure: Regenerated.
	* configure.ac (tm_d_file): New variable.
	(tm_d_file_list, tm_d_include_list, d_target_objs): Add substitutes.
	* doc/contrib.texi (Contributors): Add self for the D frontend.
	* doc/frontends.texi (G++ and GCC): Mention D as a supported language.
	* doc/install.texi (Configuration): Mention libphobos as an option for
	--enable-shared.  Mention d as an option for --enable-languages.
	(Testing): Mention check-d as a target.
	* doc/invoke.texi (Overall Options): Mention .d, .dd, and .di as file
	name suffixes.  Mention d as a -x option.
	* doc/sourcebuild.texi (Top Level): Mention libphobos.
	* doc/standards.texi (Standards): Add section on D language.
	* doc/tm.texi: Regenerated.
	* doc/tm.texi.in: Add @node for D language and ABI, and @hook for
	TARGET_CPU_VERSIONS, TARGET_D_OS_VERSIONS, and TARGET_D_CRITSEC_SIZE.
	* dwarf2out.c (is_dlang): New function.
	(gen_compile_unit_die): Use DW_LANG_D for D.
	(declare_in_namespace): Return module die for D, instead of adding
	extra declarations into the namespace.
	(gen_namespace_die): Generate DW_TAG_module for D.
	(gen_decl_die): Handle CONST_DECLSs for D.
	(dwarf2out_decl): Likewise.
	(prune_unused_types_walk_local_classes): Handle DW_tag_interface_type.
	(prune_unused_types_walk): Handle DW_tag_interface_type same as other
	kinds of aggregates.
	* gcc.c (default_compilers): Add entries for .d, .dd and .di.
	* genhooks.c: Include d/d-target.def.

gcc/po/ChangeLog:

	* EXCLUDES: Add sources from d/dmd.

gcc/testsuite/ChangeLog:

	* gcc.misc-tests/help.exp: Add D to option descriptions check.
	* gdc.dg/asan/asan.exp: New file.
	* gdc.dg/asan/gdc272.d: New test.
	* gdc.dg/compilable.d: New test.
	* gdc.dg/dg.exp: New file.
	* gdc.dg/gdc254.d: New test.
	* gdc.dg/gdc260.d: New test.
	* gdc.dg/gdc270a.d: New test.
	* gdc.dg/gdc270b.d: New test.
	* gdc.dg/gdc282.d: New test.
	* gdc.dg/gdc283.d: New test.
	* gdc.dg/imports/gdc170.d: New test.
	* gdc.dg/imports/gdc231.d: New test.
	* gdc.dg/imports/gdc239.d: New test.
	* gdc.dg/imports/gdc241a.d: New test.
	* gdc.dg/imports/gdc241b.d: New test.
	* gdc.dg/imports/gdc251a.d: New test.
	* gdc.dg/imports/gdc251b.d: New test.
	* gdc.dg/imports/gdc253.d: New test.
	* gdc.dg/imports/gdc254a.d: New test.
	* gdc.dg/imports/gdc256.d: New test.
	* gdc.dg/imports/gdc27.d: New test.
	* gdc.dg/imports/gdcpkg256/package.d: New test.
	* gdc.dg/imports/runnable.d: New test.
	* gdc.dg/link.d: New test.
	* gdc.dg/lto/lto.exp: New file.
	* gdc.dg/lto/ltotests_0.d: New test.
	* gdc.dg/lto/ltotests_1.d: New test.
	* gdc.dg/runnable.d: New test.
	* gdc.dg/simd.d: New test.
	* gdc.test/gdc-test.exp: New file.
	* lib/gdc-dg.exp: New file.
	* lib/gdc.exp: New file.

libphobos/ChangeLog:

	* Makefile.am: New file.
	* Makefile.in: New file.
	* acinclude.m4: New file.
	* aclocal.m4: New file.
	* config.h.in: New file.
	* configure: New file.
	* configure.ac: New file.
	* d_rules.am: New file.
	* libdruntime/Makefile.am: New file.
	* libdruntime/Makefile.in: New file.
	* libdruntime/__entrypoint.di: New file.
	* libdruntime/__main.di: New file.
	* libdruntime/gcc/attribute.d: New file.
	* libdruntime/gcc/backtrace.d: New file.
	* libdruntime/gcc/builtins.d: New file.
	* libdruntime/gcc/config.d.in: New file.
	* libdruntime/gcc/deh.d: New file.
	* libdruntime/gcc/libbacktrace.d.in: New file.
	* libdruntime/gcc/unwind/arm.d: New file.
	* libdruntime/gcc/unwind/arm_common.d: New file.
	* libdruntime/gcc/unwind/c6x.d: New file.
	* libdruntime/gcc/unwind/generic.d: New file.
	* libdruntime/gcc/unwind/package.d: New file.
	* libdruntime/gcc/unwind/pe.d: New file.
	* m4/autoconf.m4: New file.
	* m4/druntime.m4: New file.
	* m4/druntime/cpu.m4: New file.
	* m4/druntime/libraries.m4: New file.
	* m4/druntime/os.m4: New file.
	* m4/gcc_support.m4: New file.
	* m4/gdc.m4: New file.
	* m4/libtool.m4: New file.
	* src/Makefile.am: New file.
	* src/Makefile.in: New file.
	* src/libgphobos.spec.in: New file.
	* testsuite/Makefile.am: New file.
	* testsuite/Makefile.in: New file.
	* testsuite/config/default.exp: New file.
	* testsuite/lib/libphobos-dg.exp: New file.
	* testsuite/lib/libphobos.exp: New file.
	* testsuite/testsuite_flags.in: New file.

From-SVN: r265573

1 files changed, 5187 insertions, 0 deletions

diff --git a/libphobos/src/std/algorithm/iteration.d b/libphobos/src/std/algorithm/iteration.d
new file mode 100644
index 0000000..7e57824
--- /dev/null
+++ b/libphobos/src/std/algorithm/iteration.d
@@ -0,0 +1,5187 @@
+// Written in the D programming language.
+/**
+This is a submodule of $(MREF std, algorithm).
+It contains generic _iteration algorithms.
+
+$(SCRIPT inhibitQuickIndex = 1;)
+$(BOOKTABLE Cheat Sheet,
+$(TR $(TH Function Name) $(TH Description))
+$(T2 cache,
+        Eagerly evaluates and caches another range's $(D front).)
+$(T2 cacheBidirectional,
+        As above, but also provides $(D back) and $(D popBack).)
+$(T2 chunkBy,
+        $(D chunkBy!((a,b) => a[1] == b[1])([[1, 1], [1, 2], [2, 2], [2, 1]]))
+        returns a range containing 3 subranges: the first with just
+        $(D [1, 1]); the second with the elements $(D [1, 2]) and $(D [2, 2]);
+        and the third with just $(D [2, 1]).)
+$(T2 cumulativeFold,
+        $(D cumulativeFold!((a, b) => a + b)([1, 2, 3, 4])) returns a
+        lazily-evaluated range containing the successive reduced values `1`,
+        `3`, `6`, `10`.)
+$(T2 each,
+        $(D each!writeln([1, 2, 3])) eagerly prints the numbers $(D 1), $(D 2)
+        and $(D 3) on their own lines.)
+$(T2 filter,
+        $(D filter!(a => a > 0)([1, -1, 2, 0, -3])) iterates over elements $(D 1)
+        and $(D 2).)
+$(T2 filterBidirectional,
+        Similar to $(D filter), but also provides $(D back) and $(D popBack) at
+        a small increase in cost.)
+$(T2 fold,
+        $(D fold!((a, b) => a + b)([1, 2, 3, 4])) returns $(D 10).)
+$(T2 group,
+        $(D group([5, 2, 2, 3, 3])) returns a range containing the tuples
+        $(D tuple(5, 1)), $(D tuple(2, 2)), and $(D tuple(3, 2)).)
+$(T2 joiner,
+        $(D joiner(["hello", "world!"], "; ")) returns a range that iterates
+        over the characters $(D "hello; world!"). No new string is created -
+        the existing inputs are iterated.)
+$(T2 map,
+        $(D map!(a => a * 2)([1, 2, 3])) lazily returns a range with the numbers
+        $(D 2), $(D 4), $(D 6).)
+$(T2 permutations,
+        Lazily computes all permutations using Heap's algorithm.)
+$(T2 reduce,
+        $(D reduce!((a, b) => a + b)([1, 2, 3, 4])) returns $(D 10).
+        This is the old implementation of `fold`.)
+$(T2 splitter,
+        Lazily splits a range by a separator.)
+$(T2 sum,
+        Same as $(D fold), but specialized for accurate summation.)
+$(T2 uniq,
+        Iterates over the unique elements in a range, which is assumed sorted.)
+)
+
+Copyright: Andrei Alexandrescu 2008-.
+
+License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
+
+Authors: $(HTTP erdani.com, Andrei Alexandrescu)
+
+Source: $(PHOBOSSRC std/algorithm/_iteration.d)
+
+Macros:
+T2=$(TR $(TDNW $(LREF $1)) $(TD $+))
+ */
+module std.algorithm.iteration;
+
+// FIXME
+import std.functional; // : unaryFun, binaryFun;
+import std.range.primitives;
+import std.traits;
+
+private template aggregate(fun...)
+if (fun.length >= 1)
+{
+    /* --Intentionally not ddoc--
+     * Aggregates elements in each subrange of the given range of ranges using
+     * the given aggregating function(s).
+     * Params:
+     *  fun = One or more aggregating functions (binary functions that return a
+     *      single _aggregate value of their arguments).
+     *  ror = A range of ranges to be aggregated.
+     *
+     * Returns:
+     * A range representing the aggregated value(s) of each subrange
+     * of the original range. If only one aggregating function is specified,
+     * each element will be the aggregated value itself; if multiple functions
+     * are specified, each element will be a tuple of the aggregated values of
+     * each respective function.
+     */
+    auto aggregate(RoR)(RoR ror)
+        if (isInputRange!RoR && isIterable!(ElementType!RoR))
+    {
+        return ror.map!(reduce!fun);
+    }
+
+    @safe unittest
+    {
+        import std.algorithm.comparison : equal, max, min;
+
+        auto data = [[4, 2, 1, 3], [4, 9, -1, 3, 2], [3]];
+
+        // Single aggregating function
+        auto agg1 = data.aggregate!max;
+        assert(agg1.equal([4, 9, 3]));
+
+        // Multiple aggregating functions
+        import std.typecons : tuple;
+        auto agg2 = data.aggregate!(max, min);
+        assert(agg2.equal([
+            tuple(4, 1),
+            tuple(9, -1),
+            tuple(3, 3)
+        ]));
+    }
+}
+
+/++
+$(D cache) eagerly evaluates $(D front) of $(D range)
+on each construction or call to $(D popFront),
+to store the result in a cache.
+The result is then directly returned when $(D front) is called,
+rather than re-evaluated.
+
+This can be a useful function to place in a chain, after functions
+that have expensive evaluation, as a lazy alternative to $(REF array, std,array).
+In particular, it can be placed after a call to $(D map), or before a call
+to $(D filter).
+
+$(D cache) may provide
+$(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives)
+iteration if needed, but since this comes at an increased cost, it must be explicitly requested via the
+call to $(D cacheBidirectional). Furthermore, a bidirectional cache will
+evaluate the "center" element twice, when there is only one element left in
+the range.
+
+$(D cache) does not provide random access primitives,
+as $(D cache) would be unable to cache the random accesses.
+If $(D Range) provides slicing primitives,
+then $(D cache) will provide the same slicing primitives,
+but $(D hasSlicing!Cache) will not yield true (as the $(REF hasSlicing, std,_range,primitives)
+trait also checks for random access).
+
+Params:
+    range = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
+
+Returns:
+    an input range with the cached values of range
++/
+auto cache(Range)(Range range)
+if (isInputRange!Range)
+{
+    return _Cache!(Range, false)(range);
+}
+
+/// ditto
+auto cacheBidirectional(Range)(Range range)
+if (isBidirectionalRange!Range)
+{
+    return _Cache!(Range, true)(range);
+}
+
+///
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range, std.stdio;
+    import std.typecons : tuple;
+
+    ulong counter = 0;
+    double fun(int x)
+    {
+        ++counter;
+        // http://en.wikipedia.org/wiki/Quartic_function
+        return ( (x + 4.0) * (x + 1.0) * (x - 1.0) * (x - 3.0) ) / 14.0 + 0.5;
+    }
+    // Without cache, with array (greedy)
+    auto result1 = iota(-4, 5).map!(a =>tuple(a, fun(a)))()
+                             .filter!(a => a[1] < 0)()
+                             .map!(a => a[0])()
+                             .array();
+
+    // the values of x that have a negative y are:
+    assert(equal(result1, [-3, -2, 2]));
+
+    // Check how many times fun was evaluated.
+    // As many times as the number of items in both source and result.
+    assert(counter == iota(-4, 5).length + result1.length);
+
+    counter = 0;
+    // Without array, with cache (lazy)
+    auto result2 = iota(-4, 5).map!(a =>tuple(a, fun(a)))()
+                             .cache()
+                             .filter!(a => a[1] < 0)()
+                             .map!(a => a[0])();
+
+    // the values of x that have a negative y are:
+    assert(equal(result2, [-3, -2, 2]));
+
+    // Check how many times fun was evaluated.
+    // Only as many times as the number of items in source.
+    assert(counter == iota(-4, 5).length);
+}
+
+/++
+Tip: $(D cache) is eager when evaluating elements. If calling front on the
+underlying _range has a side effect, it will be observable before calling
+front on the actual cached _range.
+
+Furthermore, care should be taken composing $(D cache) with $(REF take, std,_range).
+By placing $(D take) before $(D cache), then $(D cache) will be "aware"
+of when the _range ends, and correctly stop caching elements when needed.
+If calling front has no side effect though, placing $(D take) after $(D cache)
+may yield a faster _range.
+
+Either way, the resulting ranges will be equivalent, but maybe not at the
+same cost or side effects.
++/
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range;
+    int i = 0;
+
+    auto r = iota(0, 4).tee!((a){i = a;}, No.pipeOnPop);
+    auto r1 = r.take(3).cache();
+    auto r2 = r.cache().take(3);
+
+    assert(equal(r1, [0, 1, 2]));
+    assert(i == 2); //The last "seen" element was 2. The data in cache has been cleared.
+
+    assert(equal(r2, [0, 1, 2]));
+    assert(i == 3); //cache has accessed 3. It is still stored internally by cache.
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range;
+    auto a = [1, 2, 3, 4];
+    assert(equal(a.map!(a => (a - 1) * a)().cache(),                      [ 0, 2, 6, 12]));
+    assert(equal(a.map!(a => (a - 1) * a)().cacheBidirectional().retro(), [12, 6, 2,  0]));
+    auto r1 = [1, 2, 3, 4].cache()             [1 .. $];
+    auto r2 = [1, 2, 3, 4].cacheBidirectional()[1 .. $];
+    assert(equal(r1, [2, 3, 4]));
+    assert(equal(r2, [2, 3, 4]));
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+
+    //immutable test
+    static struct S
+    {
+        int i;
+        this(int i)
+        {
+            //this.i = i;
+        }
+    }
+    immutable(S)[] s = [S(1), S(2), S(3)];
+    assert(equal(s.cache(),              s));
+    assert(equal(s.cacheBidirectional(), s));
+}
+
+@safe pure nothrow unittest
+{
+    import std.algorithm.comparison : equal;
+
+    //safety etc
+    auto a = [1, 2, 3, 4];
+    assert(equal(a.cache(),              a));
+    assert(equal(a.cacheBidirectional(), a));
+}
+
+@safe unittest
+{
+    char[][] stringbufs = ["hello".dup, "world".dup];
+    auto strings = stringbufs.map!((a)=>a.idup)().cache();
+    assert(strings.front is strings.front);
+}
+
+@safe unittest
+{
+    import std.range : cycle;
+    import std.algorithm.comparison : equal;
+
+    auto c = [1, 2, 3].cycle().cache();
+    c = c[1 .. $];
+    auto d = c[0 .. 1];
+    assert(d.equal([2]));
+}
+
+@safe unittest
+{
+    static struct Range
+    {
+        bool initialized = false;
+        bool front() @property {return initialized = true;}
+        void popFront() {initialized = false;}
+        enum empty = false;
+    }
+    auto r = Range().cache();
+    assert(r.source.initialized == true);
+}
+
+private struct _Cache(R, bool bidir)
+{
+    import core.exception : RangeError;
+
+    private
+    {
+        import std.algorithm.internal : algoFormat;
+        import std.meta : AliasSeq;
+
+        alias E  = ElementType!R;
+        alias UE = Unqual!E;
+
+        R source;
+
+        static if (bidir) alias CacheTypes = AliasSeq!(UE, UE);
+        else              alias CacheTypes = AliasSeq!UE;
+        CacheTypes caches;
+
+        static assert(isAssignable!(UE, E) && is(UE : E),
+            algoFormat(
+                "Cannot instantiate range with %s because %s elements are not assignable to %s.",
+                R.stringof,
+                E.stringof,
+                UE.stringof
+            )
+        );
+    }
+
+    this(R range)
+    {
+        source = range;
+        if (!range.empty)
+        {
+             caches[0] = source.front;
+             static if (bidir)
+                 caches[1] = source.back;
+        }
+    }
+
+    static if (isInfinite!R)
+        enum empty = false;
+    else
+        bool empty() @property
+        {
+            return source.empty;
+        }
+
+    static if (hasLength!R) auto length() @property
+    {
+        return source.length;
+    }
+
+    E front() @property
+    {
+        version (assert) if (empty) throw new RangeError();
+        return caches[0];
+    }
+    static if (bidir) E back() @property
+    {
+        version (assert) if (empty) throw new RangeError();
+        return caches[1];
+    }
+
+    void popFront()
+    {
+        version (assert) if (empty) throw new RangeError();
+        source.popFront();
+        if (!source.empty)
+            caches[0] = source.front;
+        else
+            caches = CacheTypes.init;
+    }
+    static if (bidir) void popBack()
+    {
+        version (assert) if (empty) throw new RangeError();
+        source.popBack();
+        if (!source.empty)
+            caches[1] = source.back;
+        else
+            caches = CacheTypes.init;
+    }
+
+    static if (isForwardRange!R)
+    {
+        private this(R source, ref CacheTypes caches)
+        {
+            this.source = source;
+            this.caches = caches;
+        }
+        typeof(this) save() @property
+        {
+            return typeof(this)(source.save, caches);
+        }
+    }
+
+    static if (hasSlicing!R)
+    {
+        enum hasEndSlicing = is(typeof(source[size_t.max .. $]));
+
+        static if (hasEndSlicing)
+        {
+            private static struct DollarToken{}
+            enum opDollar = DollarToken.init;
+
+            auto opSlice(size_t low, DollarToken)
+            {
+                return typeof(this)(source[low .. $]);
+            }
+        }
+
+        static if (!isInfinite!R)
+        {
+            typeof(this) opSlice(size_t low, size_t high)
+            {
+                return typeof(this)(source[low .. high]);
+            }
+        }
+        else static if (hasEndSlicing)
+        {
+            auto opSlice(size_t low, size_t high)
+            in
+            {
+                assert(low <= high, "Bounds error when slicing cache.");
+            }
+            body
+            {
+                import std.range : takeExactly;
+                return this[low .. $].takeExactly(high - low);
+            }
+        }
+    }
+}
+
+/**
+$(D auto map(Range)(Range r) if (isInputRange!(Unqual!Range));)
+
+Implements the homonym function (also known as $(D transform)) present
+in many languages of functional flavor. The call $(D map!(fun)(range))
+returns a range of which elements are obtained by applying $(D fun(a))
+left to right for all elements $(D a) in $(D range). The original ranges are
+not changed. Evaluation is done lazily.
+
+Params:
+    fun = one or more transformation functions
+    r = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
+
+Returns:
+    a range with each fun applied to all the elements. If there is more than one
+    fun, the element type will be $(D Tuple) containing one element for each fun.
+
+See_Also:
+    $(HTTP en.wikipedia.org/wiki/Map_(higher-order_function), Map (higher-order function))
+*/
+template map(fun...)
+if (fun.length >= 1)
+{
+    auto map(Range)(Range r) if (isInputRange!(Unqual!Range))
+    {
+        import std.meta : AliasSeq, staticMap;
+
+        alias RE = ElementType!(Range);
+        static if (fun.length > 1)
+        {
+            import std.functional : adjoin;
+            import std.meta : staticIndexOf;
+
+            alias _funs = staticMap!(unaryFun, fun);
+            alias _fun = adjoin!_funs;
+
+            // Once DMD issue #5710 is fixed, this validation loop can be moved into a template.
+            foreach (f; _funs)
+            {
+                static assert(!is(typeof(f(RE.init)) == void),
+                    "Mapping function(s) must not return void: " ~ _funs.stringof);
+            }
+        }
+        else
+        {
+            alias _fun = unaryFun!fun;
+            alias _funs = AliasSeq!(_fun);
+
+            // Do the validation separately for single parameters due to DMD issue #15777.
+            static assert(!is(typeof(_fun(RE.init)) == void),
+                "Mapping function(s) must not return void: " ~ _funs.stringof);
+        }
+
+        return MapResult!(_fun, Range)(r);
+    }
+}
+
+///
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range : chain;
+    int[] arr1 = [ 1, 2, 3, 4 ];
+    int[] arr2 = [ 5, 6 ];
+    auto squares = map!(a => a * a)(chain(arr1, arr2));
+    assert(equal(squares, [ 1, 4, 9, 16, 25, 36 ]));
+}
+
+/**
+Multiple functions can be passed to $(D map). In that case, the
+element type of $(D map) is a tuple containing one element for each
+function.
+*/
+@safe unittest
+{
+    auto sums = [2, 4, 6, 8];
+    auto products = [1, 4, 9, 16];
+
+    size_t i = 0;
+    foreach (result; [ 1, 2, 3, 4 ].map!("a + a", "a * a"))
+    {
+        assert(result[0] == sums[i]);
+        assert(result[1] == products[i]);
+        ++i;
+    }
+}
+
+/**
+You may alias $(D map) with some function(s) to a symbol and use
+it separately:
+*/
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.conv : to;
+
+    alias stringize = map!(to!string);
+    assert(equal(stringize([ 1, 2, 3, 4 ]), [ "1", "2", "3", "4" ]));
+}
+
+@safe unittest
+{
+    // Verify workaround for DMD #15777
+
+    import std.algorithm.mutation, std.string;
+    auto foo(string[] args)
+    {
+        return args.map!strip;
+    }
+}
+
+private struct MapResult(alias fun, Range)
+{
+    alias R = Unqual!Range;
+    R _input;
+
+    static if (isBidirectionalRange!R)
+    {
+        @property auto ref back()()
+        {
+            assert(!empty, "Attempting to fetch the back of an empty map.");
+            return fun(_input.back);
+        }
+
+        void popBack()()
+        {
+            assert(!empty, "Attempting to popBack an empty map.");
+            _input.popBack();
+        }
+    }
+
+    this(R input)
+    {
+        _input = input;
+    }
+
+    static if (isInfinite!R)
+    {
+        // Propagate infinite-ness.
+        enum bool empty = false;
+    }
+    else
+    {
+        @property bool empty()
+        {
+            return _input.empty;
+        }
+    }
+
+    void popFront()
+    {
+        assert(!empty, "Attempting to popFront an empty map.");
+        _input.popFront();
+    }
+
+    @property auto ref front()
+    {
+        assert(!empty, "Attempting to fetch the front of an empty map.");
+        return fun(_input.front);
+    }
+
+    static if (isRandomAccessRange!R)
+    {
+        static if (is(typeof(_input[ulong.max])))
+            private alias opIndex_t = ulong;
+        else
+            private alias opIndex_t = uint;
+
+        auto ref opIndex(opIndex_t index)
+        {
+            return fun(_input[index]);
+        }
+    }
+
+    static if (hasLength!R)
+    {
+        @property auto length()
+        {
+            return _input.length;
+        }
+
+        alias opDollar = length;
+    }
+
+    static if (hasSlicing!R)
+    {
+        static if (is(typeof(_input[ulong.max .. ulong.max])))
+            private alias opSlice_t = ulong;
+        else
+            private alias opSlice_t = uint;
+
+        static if (hasLength!R)
+        {
+            auto opSlice(opSlice_t low, opSlice_t high)
+            {
+                return typeof(this)(_input[low .. high]);
+            }
+        }
+        else static if (is(typeof(_input[opSlice_t.max .. $])))
+        {
+            struct DollarToken{}
+            enum opDollar = DollarToken.init;
+            auto opSlice(opSlice_t low, DollarToken)
+            {
+                return typeof(this)(_input[low .. $]);
+            }
+
+            auto opSlice(opSlice_t low, opSlice_t high)
+            {
+                import std.range : takeExactly;
+                return this[low .. $].takeExactly(high - low);
+            }
+        }
+    }
+
+    static if (isForwardRange!R)
+    {
+        @property auto save()
+        {
+            return typeof(this)(_input.save);
+        }
+    }
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.conv : to;
+    import std.functional : adjoin;
+
+    alias stringize = map!(to!string);
+    assert(equal(stringize([ 1, 2, 3, 4 ]), [ "1", "2", "3", "4" ]));
+
+    uint counter;
+    alias count = map!((a) { return counter++; });
+    assert(equal(count([ 10, 2, 30, 4 ]), [ 0, 1, 2, 3 ]));
+
+    counter = 0;
+    adjoin!((a) { return counter++; }, (a) { return counter++; })(1);
+    alias countAndSquare = map!((a) { return counter++; }, (a) { return counter++; });
+    //assert(equal(countAndSquare([ 10, 2 ]), [ tuple(0u, 100), tuple(1u, 4) ]));
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.ascii : toUpper;
+    import std.internal.test.dummyrange;
+    import std.range;
+    import std.typecons : tuple;
+    import std.random : unpredictableSeed, uniform, Random;
+
+    int[] arr1 = [ 1, 2, 3, 4 ];
+    const int[] arr1Const = arr1;
+    int[] arr2 = [ 5, 6 ];
+    auto squares = map!("a * a")(arr1Const);
+    assert(squares[$ - 1] == 16);
+    assert(equal(squares, [ 1, 4, 9, 16 ][]));
+    assert(equal(map!("a * a")(chain(arr1, arr2)), [ 1, 4, 9, 16, 25, 36 ][]));
+
+    // Test the caching stuff.
+    assert(squares.back == 16);
+    auto squares2 = squares.save;
+    assert(squares2.back == 16);
+
+    assert(squares2.front == 1);
+    squares2.popFront();
+    assert(squares2.front == 4);
+    squares2.popBack();
+    assert(squares2.front == 4);
+    assert(squares2.back == 9);
+
+    assert(equal(map!("a * a")(chain(arr1, arr2)), [ 1, 4, 9, 16, 25, 36 ][]));
+
+    uint i;
+    foreach (e; map!("a", "a * a")(arr1))
+    {
+        assert(e[0] == ++i);
+        assert(e[1] == i * i);
+    }
+
+    // Test length.
+    assert(squares.length == 4);
+    assert(map!"a * a"(chain(arr1, arr2)).length == 6);
+
+    // Test indexing.
+    assert(squares[0] == 1);
+    assert(squares[1] == 4);
+    assert(squares[2] == 9);
+    assert(squares[3] == 16);
+
+    // Test slicing.
+    auto squareSlice = squares[1 .. squares.length - 1];
+    assert(equal(squareSlice, [4, 9][]));
+    assert(squareSlice.back == 9);
+    assert(squareSlice[1] == 9);
+
+    // Test on a forward range to make sure it compiles when all the fancy
+    // stuff is disabled.
+    auto fibsSquares = map!"a * a"(recurrence!("a[n-1] + a[n-2]")(1, 1));
+    assert(fibsSquares.front == 1);
+    fibsSquares.popFront();
+    fibsSquares.popFront();
+    assert(fibsSquares.front == 4);
+    fibsSquares.popFront();
+    assert(fibsSquares.front == 9);
+
+    auto repeatMap = map!"a"(repeat(1));
+    auto gen = Random(unpredictableSeed);
+    auto index = uniform(0, 1024, gen);
+    static assert(isInfinite!(typeof(repeatMap)));
+    assert(repeatMap[index] == 1);
+
+    auto intRange = map!"a"([1,2,3]);
+    static assert(isRandomAccessRange!(typeof(intRange)));
+    assert(equal(intRange, [1, 2, 3]));
+
+    foreach (DummyType; AllDummyRanges)
+    {
+        DummyType d;
+        auto m = map!"a * a"(d);
+
+        static assert(propagatesRangeType!(typeof(m), DummyType));
+        assert(equal(m, [1,4,9,16,25,36,49,64,81,100]));
+    }
+
+    //Test string access
+    string  s1 = "hello world!";
+    dstring s2 = "日本語";
+    dstring s3 = "hello world!"d;
+    auto ms1 = map!(std.ascii.toUpper)(s1);
+    auto ms2 = map!(std.ascii.toUpper)(s2);
+    auto ms3 = map!(std.ascii.toUpper)(s3);
+    static assert(!is(ms1[0])); //narrow strings can't be indexed
+    assert(ms2[0] == '日');
+    assert(ms3[0] == 'H');
+    static assert(!is(ms1[0 .. 1])); //narrow strings can't be sliced
+    assert(equal(ms2[0 .. 2], "日本"w));
+    assert(equal(ms3[0 .. 2], "HE"));
+
+    // Issue 5753
+    static void voidFun(int) {}
+    static int nonvoidFun(int) { return 0; }
+    static assert(!__traits(compiles, map!voidFun([1])));
+    static assert(!__traits(compiles, map!(voidFun, voidFun)([1])));
+    static assert(!__traits(compiles, map!(nonvoidFun, voidFun)([1])));
+    static assert(!__traits(compiles, map!(voidFun, nonvoidFun)([1])));
+    static assert(!__traits(compiles, map!(a => voidFun(a))([1])));
+
+    // Phobos issue #15480
+    auto dd = map!(z => z * z, c => c * c * c)([ 1, 2, 3, 4 ]);
+    assert(dd[0] == tuple(1, 1));
+    assert(dd[1] == tuple(4, 8));
+    assert(dd[2] == tuple(9, 27));
+    assert(dd[3] == tuple(16, 64));
+    assert(dd.length == 4);
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range;
+    auto LL = iota(1L, 4L);
+    auto m = map!"a*a"(LL);
+    assert(equal(m, [1L, 4L, 9L]));
+}
+
+@safe unittest
+{
+    import std.range : iota;
+
+    // Issue #10130 - map of iota with const step.
+    const step = 2;
+    assert(map!(i => i)(iota(0, 10, step)).walkLength == 5);
+
+    // Need these to all by const to repro the float case, due to the
+    // CommonType template used in the float specialization of iota.
+    const floatBegin = 0.0;
+    const floatEnd = 1.0;
+    const floatStep = 0.02;
+    assert(map!(i => i)(iota(floatBegin, floatEnd, floatStep)).walkLength == 50);
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range;
+    //slicing infinites
+    auto rr = iota(0, 5).cycle().map!"a * a"();
+    alias RR = typeof(rr);
+    static assert(hasSlicing!RR);
+    rr = rr[6 .. $]; //Advances 1 cycle and 1 unit
+    assert(equal(rr[0 .. 5], [1, 4, 9, 16, 0]));
+}
+
+@safe unittest
+{
+    import std.range;
+    struct S {int* p;}
+    auto m = immutable(S).init.repeat().map!"a".save;
+    assert(m.front == immutable(S)(null));
+}
+
+// each
+/**
+Eagerly iterates over $(D r) and calls $(D pred) over _each element.
+
+If no predicate is specified, $(D each) will default to doing nothing
+but consuming the entire range. $(D .front) will be evaluated, but this
+can be avoided by explicitly specifying a predicate lambda with a
+$(D lazy) parameter.
+
+$(D each) also supports $(D opApply)-based iterators, so it will work
+with e.g. $(REF parallel, std,parallelism).
+
+Params:
+    pred = predicate to apply to each element of the range
+    r = range or iterable over which each iterates
+
+See_Also: $(REF tee, std,range)
+
+ */
+template each(alias pred = "a")
+{
+    import std.meta : AliasSeq;
+    import std.traits : Parameters;
+
+private:
+    alias BinaryArgs = AliasSeq!(pred, "i", "a");
+
+    enum isRangeUnaryIterable(R) =
+        is(typeof(unaryFun!pred(R.init.front)));
+
+    enum isRangeBinaryIterable(R) =
+        is(typeof(binaryFun!BinaryArgs(0, R.init.front)));
+
+    enum isRangeIterable(R) =
+        isInputRange!R &&
+        (isRangeUnaryIterable!R || isRangeBinaryIterable!R);
+
+    enum isForeachUnaryIterable(R) =
+        is(typeof((R r) {
+            foreach (ref a; r)
+                cast(void) unaryFun!pred(a);
+        }));
+
+    enum isForeachBinaryIterable(R) =
+        is(typeof((R r) {
+            foreach (ref i, ref a; r)
+                cast(void) binaryFun!BinaryArgs(i, a);
+        }));
+
+    enum isForeachIterable(R) =
+        (!isForwardRange!R || isDynamicArray!R) &&
+        (isForeachUnaryIterable!R || isForeachBinaryIterable!R);
+
+public:
+    void each(Range)(Range r)
+    if (!isForeachIterable!Range && (
+        isRangeIterable!Range ||
+        __traits(compiles, typeof(r.front).length)))
+    {
+        static if (isRangeIterable!Range)
+        {
+            debug(each) pragma(msg, "Using while for ", Range.stringof);
+            static if (isRangeUnaryIterable!Range)
+            {
+                while (!r.empty)
+                {
+                    cast(void) unaryFun!pred(r.front);
+                    r.popFront();
+                }
+            }
+            else // if (isRangeBinaryIterable!Range)
+            {
+                size_t i = 0;
+                while (!r.empty)
+                {
+                    cast(void) binaryFun!BinaryArgs(i, r.front);
+                    r.popFront();
+                    i++;
+                }
+            }
+        }
+        else
+        {
+            // range interface with >2 parameters.
+            for (auto range = r; !range.empty; range.popFront())
+                pred(range.front.expand);
+        }
+    }
+
+    void each(Iterable)(auto ref Iterable r)
+    if (isForeachIterable!Iterable ||
+        __traits(compiles, Parameters!(Parameters!(r.opApply))))
+    {
+        static if (isForeachIterable!Iterable)
+        {
+            debug(each) pragma(msg, "Using foreach for ", Iterable.stringof);
+            static if (isForeachUnaryIterable!Iterable)
+            {
+                foreach (ref e; r)
+                    cast(void) unaryFun!pred(e);
+            }
+            else // if (isForeachBinaryIterable!Iterable)
+            {
+                foreach (ref i, ref e; r)
+                    cast(void) binaryFun!BinaryArgs(i, e);
+            }
+        }
+        else
+        {
+            // opApply with >2 parameters. count the delegate args.
+            // only works if it is not templated (otherwise we cannot count the args)
+            auto dg(Parameters!(Parameters!(r.opApply)) params) {
+                pred(params);
+                return 0; // tells opApply to continue iteration
+            }
+            r.opApply(&dg);
+        }
+    }
+}
+
+///
+@system unittest
+{
+    import std.range : iota;
+
+    long[] arr;
+    iota(5).each!(n => arr ~= n);
+    assert(arr == [0, 1, 2, 3, 4]);
+
+    // If the range supports it, the value can be mutated in place
+    arr.each!((ref n) => n++);
+    assert(arr == [1, 2, 3, 4, 5]);
+
+    arr.each!"a++";
+    assert(arr == [2, 3, 4, 5, 6]);
+
+    // by-ref lambdas are not allowed for non-ref ranges
+    static assert(!is(typeof(arr.map!(n => n).each!((ref n) => n++))));
+
+    // The default predicate consumes the range
+    auto m = arr.map!(n => n);
+    (&m).each();
+    assert(m.empty);
+
+    // Indexes are also available for in-place mutations
+    arr[] = 0;
+    arr.each!"a=i"();
+    assert(arr == [0, 1, 2, 3, 4]);
+
+    // opApply iterators work as well
+    static class S
+    {
+        int x;
+        int opApply(scope int delegate(ref int _x) dg) { return dg(x); }
+    }
+
+    auto s = new S;
+    s.each!"a++";
+    assert(s.x == 1);
+}
+
+// binary foreach with two ref args
+@system unittest
+{
+    import std.range : lockstep;
+
+    auto a = [ 1, 2, 3 ];
+    auto b = [ 2, 3, 4 ];
+
+    a.lockstep(b).each!((ref x, ref y) { ++x; ++y; });
+
+    assert(a == [ 2, 3, 4 ]);
+    assert(b == [ 3, 4, 5 ]);
+}
+
+// #15358: application of `each` with >2 args (opApply)
+@system unittest
+{
+    import std.range : lockstep;
+    auto a = [0,1,2];
+    auto b = [3,4,5];
+    auto c = [6,7,8];
+
+    lockstep(a, b, c).each!((ref x, ref y, ref z) { ++x; ++y; ++z; });
+
+    assert(a == [1,2,3]);
+    assert(b == [4,5,6]);
+    assert(c == [7,8,9]);
+}
+
+// #15358: application of `each` with >2 args (range interface)
+@safe unittest
+{
+    import std.range : zip;
+    auto a = [0,1,2];
+    auto b = [3,4,5];
+    auto c = [6,7,8];
+
+    int[] res;
+
+    zip(a, b, c).each!((x, y, z) { res ~= x + y + z; });
+
+    assert(res == [9, 12, 15]);
+}
+
+// #16255: `each` on opApply doesn't support ref
+@safe unittest
+{
+    int[] dynamicArray = [1, 2, 3, 4, 5];
+    int[5] staticArray = [1, 2, 3, 4, 5];
+
+    dynamicArray.each!((ref x) => x++);
+    assert(dynamicArray == [2, 3, 4, 5, 6]);
+
+    staticArray.each!((ref x) => x++);
+    assert(staticArray == [2, 3, 4, 5, 6]);
+
+    staticArray[].each!((ref x) => x++);
+    assert(staticArray == [3, 4, 5, 6, 7]);
+}
+
+// #16255: `each` on opApply doesn't support ref
+@system unittest
+{
+    struct S
+    {
+       int x;
+       int opApply(int delegate(ref int _x) dg) { return dg(x); }
+    }
+
+    S s;
+    foreach (ref a; s) ++a;
+    assert(s.x == 1);
+    s.each!"++a";
+    assert(s.x == 2);
+}
+
+// filter
+/**
+$(D auto filter(Range)(Range rs) if (isInputRange!(Unqual!Range));)
+
+Implements the higher order _filter function. The predicate is passed to
+$(REF unaryFun, std,functional), and can either accept a string, or any callable
+that can be executed via $(D pred(element)).
+
+Params:
+    predicate = Function to apply to each element of range
+    range = Input range of elements
+
+Returns:
+    $(D filter!(predicate)(range)) returns a new range containing only elements $(D x) in $(D range) for
+    which $(D predicate(x)) returns $(D true).
+
+See_Also:
+    $(HTTP en.wikipedia.org/wiki/Filter_(higher-order_function), Filter (higher-order function))
+ */
+template filter(alias predicate)
+if (is(typeof(unaryFun!predicate)))
+{
+    auto filter(Range)(Range range) if (isInputRange!(Unqual!Range))
+    {
+        return FilterResult!(unaryFun!predicate, Range)(range);
+    }
+}
+
+///
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.math : approxEqual;
+    import std.range;
+
+    int[] arr = [ 1, 2, 3, 4, 5 ];
+
+    // Sum all elements
+    auto small = filter!(a => a < 3)(arr);
+    assert(equal(small, [ 1, 2 ]));
+
+    // Sum again, but with Uniform Function Call Syntax (UFCS)
+    auto sum = arr.filter!(a => a < 3);
+    assert(equal(sum, [ 1, 2 ]));
+
+    // In combination with chain() to span multiple ranges
+    int[] a = [ 3, -2, 400 ];
+    int[] b = [ 100, -101, 102 ];
+    auto r = chain(a, b).filter!(a => a > 0);
+    assert(equal(r, [ 3, 400, 100, 102 ]));
+
+    // Mixing convertible types is fair game, too
+    double[] c = [ 2.5, 3.0 ];
+    auto r1 = chain(c, a, b).filter!(a => cast(int) a != a);
+    assert(approxEqual(r1, [ 2.5 ]));
+}
+
+private struct FilterResult(alias pred, Range)
+{
+    alias R = Unqual!Range;
+    R _input;
+    private bool _primed;
+
+    private void prime()
+    {
+        if (_primed) return;
+        while (!_input.empty && !pred(_input.front))
+        {
+            _input.popFront();
+        }
+        _primed = true;
+    }
+
+    this(R r)
+    {
+        _input = r;
+    }
+
+    private this(R r, bool primed)
+    {
+        _input = r;
+        _primed = primed;
+    }
+
+    auto opSlice() { return this; }
+
+    static if (isInfinite!Range)
+    {
+        enum bool empty = false;
+    }
+    else
+    {
+        @property bool empty() { prime; return _input.empty; }
+    }
+
+    void popFront()
+    {
+        do
+        {
+            _input.popFront();
+        } while (!_input.empty && !pred(_input.front));
+        _primed = true;
+    }
+
+    @property auto ref front()
+    {
+        prime;
+        assert(!empty, "Attempting to fetch the front of an empty filter.");
+        return _input.front;
+    }
+
+    static if (isForwardRange!R)
+    {
+        @property auto save()
+        {
+            return typeof(this)(_input.save, _primed);
+        }
+    }
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.internal.test.dummyrange;
+    import std.range;
+
+    auto shouldNotLoop4ever = repeat(1).filter!(x => x % 2 == 0);
+    static assert(isInfinite!(typeof(shouldNotLoop4ever)));
+    assert(!shouldNotLoop4ever.empty);
+
+    int[] a = [ 3, 4, 2 ];
+    auto r = filter!("a > 3")(a);
+    static assert(isForwardRange!(typeof(r)));
+    assert(equal(r, [ 4 ][]));
+
+    a = [ 1, 22, 3, 42, 5 ];
+    auto under10 = filter!("a < 10")(a);
+    assert(equal(under10, [1, 3, 5][]));
+    static assert(isForwardRange!(typeof(under10)));
+    under10.front = 4;
+    assert(equal(under10, [4, 3, 5][]));
+    under10.front = 40;
+    assert(equal(under10, [40, 3, 5][]));
+    under10.front = 1;
+
+    auto infinite = filter!"a > 2"(repeat(3));
+    static assert(isInfinite!(typeof(infinite)));
+    static assert(isForwardRange!(typeof(infinite)));
+    assert(infinite.front == 3);
+
+    foreach (DummyType; AllDummyRanges)
+    {
+        DummyType d;
+        auto f = filter!"a & 1"(d);
+        assert(equal(f, [1,3,5,7,9]));
+
+        static if (isForwardRange!DummyType)
+        {
+            static assert(isForwardRange!(typeof(f)));
+        }
+    }
+
+    // With delegates
+    int x = 10;
+    int overX(int a) { return a > x; }
+    typeof(filter!overX(a)) getFilter()
+    {
+        return filter!overX(a);
+    }
+    auto r1 = getFilter();
+    assert(equal(r1, [22, 42]));
+
+    // With chain
+    auto nums = [0,1,2,3,4];
+    assert(equal(filter!overX(chain(a, nums)), [22, 42]));
+
+    // With copying of inner struct Filter to Map
+    auto arr = [1,2,3,4,5];
+    auto m = map!"a + 1"(filter!"a < 4"(arr));
+    assert(equal(m, [2, 3, 4]));
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+
+    int[] a = [ 3, 4 ];
+    const aConst = a;
+    auto r = filter!("a > 3")(aConst);
+    assert(equal(r, [ 4 ][]));
+
+    a = [ 1, 22, 3, 42, 5 ];
+    auto under10 = filter!("a < 10")(a);
+    assert(equal(under10, [1, 3, 5][]));
+    assert(equal(under10.save, [1, 3, 5][]));
+    assert(equal(under10.save, under10));
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.functional : compose, pipe;
+
+    assert(equal(compose!(map!"2 * a", filter!"a & 1")([1,2,3,4,5]),
+                    [2,6,10]));
+    assert(equal(pipe!(filter!"a & 1", map!"2 * a")([1,2,3,4,5]),
+            [2,6,10]));
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+
+    int x = 10;
+    int underX(int a) { return a < x; }
+    const(int)[] list = [ 1, 2, 10, 11, 3, 4 ];
+    assert(equal(filter!underX(list), [ 1, 2, 3, 4 ]));
+}
+
+/**
+ * $(D auto filterBidirectional(Range)(Range r) if (isBidirectionalRange!(Unqual!Range));)
+ *
+ * Similar to $(D filter), except it defines a
+ * $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives).
+ * There is a speed disadvantage - the constructor spends time
+ * finding the last element in the range that satisfies the filtering
+ * condition (in addition to finding the first one). The advantage is
+ * that the filtered range can be spanned from both directions. Also,
+ * $(REF retro, std,range) can be applied against the filtered range.
+ *
+ * The predicate is passed to $(REF unaryFun, std,functional), and can either
+ * accept a string, or any callable that can be executed via $(D pred(element)).
+ *
+ * Params:
+ *     pred = Function to apply to each element of range
+ *     r = Bidirectional range of elements
+ *
+ * Returns:
+ *     a new range containing only the elements in r for which pred returns $(D true).
+ */
+template filterBidirectional(alias pred)
+{
+    auto filterBidirectional(Range)(Range r) if (isBidirectionalRange!(Unqual!Range))
+    {
+        return FilterBidiResult!(unaryFun!pred, Range)(r);
+    }
+}
+
+///
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range;
+
+    int[] arr = [ 1, 2, 3, 4, 5 ];
+    auto small = filterBidirectional!("a < 3")(arr);
+    static assert(isBidirectionalRange!(typeof(small)));
+    assert(small.back == 2);
+    assert(equal(small, [ 1, 2 ]));
+    assert(equal(retro(small), [ 2, 1 ]));
+    // In combination with chain() to span multiple ranges
+    int[] a = [ 3, -2, 400 ];
+    int[] b = [ 100, -101, 102 ];
+    auto r = filterBidirectional!("a > 0")(chain(a, b));
+    assert(r.back == 102);
+}
+
+private struct FilterBidiResult(alias pred, Range)
+{
+    alias R = Unqual!Range;
+    R _input;
+
+    this(R r)
+    {
+        _input = r;
+        while (!_input.empty && !pred(_input.front)) _input.popFront();
+        while (!_input.empty && !pred(_input.back)) _input.popBack();
+    }
+
+    @property bool empty() { return _input.empty; }
+
+    void popFront()
+    {
+        do
+        {
+            _input.popFront();
+        } while (!_input.empty && !pred(_input.front));
+    }
+
+    @property auto ref front()
+    {
+        assert(!empty, "Attempting to fetch the front of an empty filterBidirectional.");
+        return _input.front;
+    }
+
+    void popBack()
+    {
+        do
+        {
+            _input.popBack();
+        } while (!_input.empty && !pred(_input.back));
+    }
+
+    @property auto ref back()
+    {
+        assert(!empty, "Attempting to fetch the back of an empty filterBidirectional.");
+        return _input.back;
+    }
+
+    @property auto save()
+    {
+        return typeof(this)(_input.save);
+    }
+}
+
+/**
+Groups consecutively equivalent elements into a single tuple of the element and
+the number of its repetitions.
+
+Similarly to $(D uniq), $(D group) produces a range that iterates over unique
+consecutive elements of the given range. Each element of this range is a tuple
+of the element and the number of times it is repeated in the original range.
+Equivalence of elements is assessed by using the predicate $(D pred), which
+defaults to $(D "a == b").  The predicate is passed to $(REF binaryFun, std,functional),
+and can either accept a string, or any callable that can be executed via
+$(D pred(element, element)).
+
+Params:
+    pred = Binary predicate for determining equivalence of two elements.
+    r = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to
+        iterate over.
+
+Returns: A range of elements of type $(D Tuple!(ElementType!R, uint)),
+representing each consecutively unique element and its respective number of
+occurrences in that run.  This will be an input range if $(D R) is an input
+range, and a forward range in all other cases.
+
+See_Also: $(LREF chunkBy), which chunks an input range into subranges
+    of equivalent adjacent elements.
+*/
+Group!(pred, Range) group(alias pred = "a == b", Range)(Range r)
+{
+    return typeof(return)(r);
+}
+
+/// ditto
+struct Group(alias pred, R)
+if (isInputRange!R)
+{
+    import std.typecons : Rebindable, tuple, Tuple;
+
+    private alias comp = binaryFun!pred;
+
+    private alias E = ElementType!R;
+    static if ((is(E == class) || is(E == interface)) &&
+               (is(E == const) || is(E == immutable)))
+    {
+        private alias MutableE = Rebindable!E;
+    }
+    else static if (is(E : Unqual!E))
+    {
+        private alias MutableE = Unqual!E;
+    }
+    else
+    {
+        private alias MutableE = E;
+    }
+
+    private R _input;
+    private Tuple!(MutableE, uint) _current;
+
+    ///
+    this(R input)
+    {
+        _input = input;
+        if (!_input.empty) popFront();
+    }
+
+    ///
+    void popFront()
+    {
+        if (_input.empty)
+        {
+            _current[1] = 0;
+        }
+        else
+        {
+            _current = tuple(_input.front, 1u);
+            _input.popFront();
+            while (!_input.empty && comp(_current[0], _input.front))
+            {
+                ++_current[1];
+                _input.popFront();
+            }
+        }
+    }
+
+    static if (isInfinite!R)
+    {
+        ///
+        enum bool empty = false;  // Propagate infiniteness.
+    }
+    else
+    {
+        ///
+        @property bool empty()
+        {
+            return _current[1] == 0;
+        }
+    }
+
+    ///
+    @property auto ref front()
+    {
+        assert(!empty, "Attempting to fetch the front of an empty Group.");
+        return _current;
+    }
+
+    static if (isForwardRange!R)
+    {
+        ///
+        @property typeof(this) save() {
+            typeof(this) ret = this;
+            ret._input = this._input.save;
+            ret._current = this._current;
+            return ret;
+        }
+    }
+}
+
+///
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.typecons : tuple, Tuple;
+
+    int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
+    assert(equal(group(arr), [ tuple(1, 1u), tuple(2, 4u), tuple(3, 1u),
+        tuple(4, 3u), tuple(5, 1u) ][]));
+}
+
+/**
+ * Using group, an associative array can be easily generated with the count of each
+ * unique element in the range.
+ */
+@safe unittest
+{
+    import std.algorithm.sorting : sort;
+    import std.array : assocArray;
+
+    uint[string] result;
+    auto range = ["a", "b", "a", "c", "b", "c", "c", "d", "e"];
+    result = range.sort!((a, b) => a < b)
+        .group
+        .assocArray;
+
+    assert(result == ["a": 2U, "b": 2U, "c": 3U, "d": 1U, "e": 1U]);
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.internal.test.dummyrange;
+    import std.typecons : tuple, Tuple;
+
+    int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
+    assert(equal(group(arr), [ tuple(1, 1u), tuple(2, 4u), tuple(3, 1u),
+                            tuple(4, 3u), tuple(5, 1u) ][]));
+    static assert(isForwardRange!(typeof(group(arr))));
+
+    foreach (DummyType; AllDummyRanges)
+    {
+        DummyType d;
+        auto g = group(d);
+
+        static assert(d.rt == RangeType.Input || isForwardRange!(typeof(g)));
+
+        assert(equal(g, [tuple(1, 1u), tuple(2, 1u), tuple(3, 1u), tuple(4, 1u),
+            tuple(5, 1u), tuple(6, 1u), tuple(7, 1u), tuple(8, 1u),
+            tuple(9, 1u), tuple(10, 1u)]));
+    }
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.typecons : tuple;
+
+    // Issue 13857
+    immutable(int)[] a1 = [1,1,2,2,2,3,4,4,5,6,6,7,8,9,9,9];
+    auto g1 = group(a1);
+    assert(equal(g1, [ tuple(1, 2u), tuple(2, 3u), tuple(3, 1u),
+                       tuple(4, 2u), tuple(5, 1u), tuple(6, 2u),
+                       tuple(7, 1u), tuple(8, 1u), tuple(9, 3u)
+                     ]));
+
+    // Issue 13162
+    immutable(ubyte)[] a2 = [1, 1, 1, 0, 0, 0];
+    auto g2 = a2.group;
+    assert(equal(g2, [ tuple(1, 3u), tuple(0, 3u) ]));
+
+    // Issue 10104
+    const a3 = [1, 1, 2, 2];
+    auto g3 = a3.group;
+    assert(equal(g3, [ tuple(1, 2u), tuple(2, 2u) ]));
+
+    interface I {}
+    class C : I {}
+    const C[] a4 = [new const C()];
+    auto g4 = a4.group!"a is b";
+    assert(g4.front[1] == 1);
+
+    immutable I[] a5 = [new immutable C()];
+    auto g5 = a5.group!"a is b";
+    assert(g5.front[1] == 1);
+
+    const(int[][]) a6 = [[1], [1]];
+    auto g6 = a6.group;
+    assert(equal(g6.front[0], [1]));
+}
+
+// Used by implementation of chunkBy for non-forward input ranges.
+private struct ChunkByChunkImpl(alias pred, Range)
+if (isInputRange!Range && !isForwardRange!Range)
+{
+    alias fun = binaryFun!pred;
+
+    private Range r;
+    private ElementType!Range prev;
+
+    this(Range range, ElementType!Range _prev)
+    {
+        r = range;
+        prev = _prev;
+    }
+
+    @property bool empty()
+    {
+        return r.empty || !fun(prev, r.front);
+    }
+
+    @property ElementType!Range front() { return r.front; }
+    void popFront() { r.popFront(); }
+}
+
+private template ChunkByImplIsUnary(alias pred, Range)
+{
+    static if (is(typeof(binaryFun!pred(ElementType!Range.init,
+                                        ElementType!Range.init)) : bool))
+        enum ChunkByImplIsUnary = false;
+    else static if (is(typeof(
+            unaryFun!pred(ElementType!Range.init) ==
+            unaryFun!pred(ElementType!Range.init))))
+        enum ChunkByImplIsUnary = true;
+    else
+        static assert(0, "chunkBy expects either a binary predicate or "~
+                         "a unary predicate on range elements of type: "~
+                         ElementType!Range.stringof);
+}
+
+// Implementation of chunkBy for non-forward input ranges.
+private struct ChunkByImpl(alias pred, Range)
+if (isInputRange!Range && !isForwardRange!Range)
+{
+    enum bool isUnary = ChunkByImplIsUnary!(pred, Range);
+
+    static if (isUnary)
+        alias eq = binaryFun!((a, b) => unaryFun!pred(a) == unaryFun!pred(b));
+    else
+        alias eq = binaryFun!pred;
+
+    private Range r;
+    private ElementType!Range _prev;
+
+    this(Range _r)
+    {
+        r = _r;
+        if (!empty)
+        {
+            // Check reflexivity if predicate is claimed to be an equivalence
+            // relation.
+            assert(eq(r.front, r.front),
+                   "predicate is not reflexive");
+
+            // _prev's type may be a nested struct, so must be initialized
+            // directly in the constructor (cannot call savePred()).
+            _prev = r.front;
+        }
+        else
+        {
+            // We won't use _prev, but must be initialized.
+            _prev = typeof(_prev).init;
+        }
+    }
+    @property bool empty() { return r.empty; }
+
+    @property auto front()
+    {
+        static if (isUnary)
+        {
+            import std.typecons : tuple;
+            return tuple(unaryFun!pred(_prev),
+                         ChunkByChunkImpl!(eq, Range)(r, _prev));
+        }
+        else
+        {
+            return ChunkByChunkImpl!(eq, Range)(r, _prev);
+        }
+    }
+
+    void popFront()
+    {
+        while (!r.empty)
+        {
+            if (!eq(_prev, r.front))
+            {
+                _prev = r.front;
+                break;
+            }
+            r.popFront();
+        }
+    }
+}
+
+// Single-pass implementation of chunkBy for forward ranges.
+private struct ChunkByImpl(alias pred, Range)
+if (isForwardRange!Range)
+{
+    import std.typecons : RefCounted;
+
+    enum bool isUnary = ChunkByImplIsUnary!(pred, Range);
+
+    static if (isUnary)
+        alias eq = binaryFun!((a, b) => unaryFun!pred(a) == unaryFun!pred(b));
+    else
+        alias eq = binaryFun!pred;
+
+    // Outer range
+    static struct Impl
+    {
+        size_t groupNum;
+        Range  current;
+        Range  next;
+    }
+
+    // Inner range
+    static struct Group
+    {
+        private size_t groupNum;
+        private Range  start;
+        private Range  current;
+
+        private RefCounted!Impl mothership;
+
+        this(RefCounted!Impl origin)
+        {
+            groupNum = origin.groupNum;
+
+            start = origin.current.save;
+            current = origin.current.save;
+            assert(!start.empty);
+
+            mothership = origin;
+
+            // Note: this requires reflexivity.
+            assert(eq(start.front, current.front),
+                   "predicate is not reflexive");
+        }
+
+        @property bool empty() { return groupNum == size_t.max; }
+        @property auto ref front() { return current.front; }
+
+        void popFront()
+        {
+            current.popFront();
+
+            // Note: this requires transitivity.
+            if (current.empty || !eq(start.front, current.front))
+            {
+                if (groupNum == mothership.groupNum)
+                {
+                    // If parent range hasn't moved on yet, help it along by
+                    // saving location of start of next Group.
+                    mothership.next = current.save;
+                }
+
+                groupNum = size_t.max;
+            }
+        }
+
+        @property auto save()
+        {
+            auto copy = this;
+            copy.current = current.save;
+            return copy;
+        }
+    }
+    static assert(isForwardRange!Group);
+
+    private RefCounted!Impl impl;
+
+    this(Range r)
+    {
+        impl = RefCounted!Impl(0, r, r.save);
+    }
+
+    @property bool empty() { return impl.current.empty; }
+
+    @property auto front()
+    {
+        static if (isUnary)
+        {
+            import std.typecons : tuple;
+            return tuple(unaryFun!pred(impl.current.front), Group(impl));
+        }
+        else
+        {
+            return Group(impl);
+        }
+    }
+
+    void popFront()
+    {
+        // Scan for next group. If we're lucky, one of our Groups would have
+        // already set .next to the start of the next group, in which case the
+        // loop is skipped.
+        while (!impl.next.empty && eq(impl.current.front, impl.next.front))
+        {
+            impl.next.popFront();
+        }
+
+        impl.current = impl.next.save;
+
+        // Indicate to any remaining Groups that we have moved on.
+        impl.groupNum++;
+    }
+
+    @property auto save()
+    {
+        // Note: the new copy of the range will be detached from any existing
+        // satellite Groups, and will not benefit from the .next acceleration.
+        return typeof(this)(impl.current.save);
+    }
+
+    static assert(isForwardRange!(typeof(this)));
+}
+
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+
+    size_t popCount = 0;
+    class RefFwdRange
+    {
+        int[]  impl;
+
+        @safe nothrow:
+
+        this(int[] data) { impl = data; }
+        @property bool empty() { return impl.empty; }
+        @property auto ref front() { return impl.front; }
+        void popFront()
+        {
+            impl.popFront();
+            popCount++;
+        }
+        @property auto save() { return new RefFwdRange(impl); }
+    }
+    static assert(isForwardRange!RefFwdRange);
+
+    auto testdata = new RefFwdRange([1, 3, 5, 2, 4, 7, 6, 8, 9]);
+    auto groups = testdata.chunkBy!((a,b) => (a % 2) == (b % 2));
+    auto outerSave1 = groups.save;
+
+    // Sanity test
+    assert(groups.equal!equal([[1, 3, 5], [2, 4], [7], [6, 8], [9]]));
+    assert(groups.empty);
+
+    // Performance test for single-traversal use case: popFront should not have
+    // been called more times than there are elements if we traversed the
+    // segmented range exactly once.
+    assert(popCount == 9);
+
+    // Outer range .save test
+    groups = outerSave1.save;
+    assert(!groups.empty);
+
+    // Inner range .save test
+    auto grp1 = groups.front.save;
+    auto grp1b = grp1.save;
+    assert(grp1b.equal([1, 3, 5]));
+    assert(grp1.save.equal([1, 3, 5]));
+
+    // Inner range should remain consistent after outer range has moved on.
+    groups.popFront();
+    assert(grp1.save.equal([1, 3, 5]));
+
+    // Inner range should not be affected by subsequent inner ranges.
+    assert(groups.front.equal([2, 4]));
+    assert(grp1.save.equal([1, 3, 5]));
+}
+
+/**
+ * Chunks an input range into subranges of equivalent adjacent elements.
+ * In other languages this is often called `partitionBy`, `groupBy`
+ * or `sliceWhen`.
+ *
+ * Equivalence is defined by the predicate $(D pred), which can be either
+ * binary, which is passed to $(REF binaryFun, std,functional), or unary, which is
+ * passed to $(REF unaryFun, std,functional). In the binary form, two _range elements
+ * $(D a) and $(D b) are considered equivalent if $(D pred(a,b)) is true. In
+ * unary form, two elements are considered equivalent if $(D pred(a) == pred(b))
+ * is true.
+ *
+ * This predicate must be an equivalence relation, that is, it must be
+ * reflexive ($(D pred(x,x)) is always true), symmetric
+ * ($(D pred(x,y) == pred(y,x))), and transitive ($(D pred(x,y) && pred(y,z))
+ * implies $(D pred(x,z))). If this is not the case, the range returned by
+ * chunkBy may assert at runtime or behave erratically.
+ *
+ * Params:
+ *  pred = Predicate for determining equivalence.
+ *  r = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to be chunked.
+ *
+ * Returns: With a binary predicate, a range of ranges is returned in which
+ * all elements in a given subrange are equivalent under the given predicate.
+ * With a unary predicate, a range of tuples is returned, with the tuple
+ * consisting of the result of the unary predicate for each subrange, and the
+ * subrange itself.
+ *
+ * Notes:
+ *
+ * Equivalent elements separated by an intervening non-equivalent element will
+ * appear in separate subranges; this function only considers adjacent
+ * equivalence. Elements in the subranges will always appear in the same order
+ * they appear in the original range.
+ *
+ * See_also:
+ * $(LREF group), which collapses adjacent equivalent elements into a single
+ * element.
+ */
+auto chunkBy(alias pred, Range)(Range r)
+if (isInputRange!Range)
+{
+    return ChunkByImpl!(pred, Range)(r);
+}
+
+/// Showing usage with binary predicate:
+/*FIXME: @safe*/ @system unittest
+{
+    import std.algorithm.comparison : equal;
+
+    // Grouping by particular attribute of each element:
+    auto data = [
+        [1, 1],
+        [1, 2],
+        [2, 2],
+        [2, 3]
+    ];
+
+    auto r1 = data.chunkBy!((a,b) => a[0] == b[0]);
+    assert(r1.equal!equal([
+        [[1, 1], [1, 2]],
+        [[2, 2], [2, 3]]
+    ]));
+
+    auto r2 = data.chunkBy!((a,b) => a[1] == b[1]);
+    assert(r2.equal!equal([
+        [[1, 1]],
+        [[1, 2], [2, 2]],
+        [[2, 3]]
+    ]));
+}
+
+version (none) // this example requires support for non-equivalence relations
+@safe unittest
+{
+    // Grouping by maximum adjacent difference:
+    import std.math : abs;
+    auto r3 = [1, 3, 2, 5, 4, 9, 10].chunkBy!((a, b) => abs(a-b) < 3);
+    assert(r3.equal!equal([
+        [1, 3, 2],
+        [5, 4],
+        [9, 10]
+    ]));
+
+}
+
+/// Showing usage with unary predicate:
+/* FIXME: pure @safe nothrow*/ @system unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range.primitives;
+    import std.typecons : tuple;
+
+    // Grouping by particular attribute of each element:
+    auto range =
+    [
+        [1, 1],
+        [1, 1],
+        [1, 2],
+        [2, 2],
+        [2, 3],
+        [2, 3],
+        [3, 3]
+    ];
+
+    auto byX = chunkBy!(a => a[0])(range);
+    auto expected1 =
+    [
+        tuple(1, [[1, 1], [1, 1], [1, 2]]),
+        tuple(2, [[2, 2], [2, 3], [2, 3]]),
+        tuple(3, [[3, 3]])
+    ];
+    foreach (e; byX)
+    {
+        assert(!expected1.empty);
+        assert(e[0] == expected1.front[0]);
+        assert(e[1].equal(expected1.front[1]));
+        expected1.popFront();
+    }
+
+    auto byY = chunkBy!(a => a[1])(range);
+    auto expected2 =
+    [
+        tuple(1, [[1, 1], [1, 1]]),
+        tuple(2, [[1, 2], [2, 2]]),
+        tuple(3, [[2, 3], [2, 3], [3, 3]])
+    ];
+    foreach (e; byY)
+    {
+        assert(!expected2.empty);
+        assert(e[0] == expected2.front[0]);
+        assert(e[1].equal(expected2.front[1]));
+        expected2.popFront();
+    }
+}
+
+/*FIXME: pure @safe nothrow*/ @system unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.typecons : tuple;
+
+    struct Item { int x, y; }
+
+    // Force R to have only an input range API with reference semantics, so
+    // that we're not unknowingly making use of array semantics outside of the
+    // range API.
+    class RefInputRange(R)
+    {
+        R data;
+        this(R _data) pure @safe nothrow { data = _data; }
+        @property bool empty() pure @safe nothrow { return data.empty; }
+        @property auto front() pure @safe nothrow { return data.front; }
+        void popFront() pure @safe nothrow { data.popFront(); }
+    }
+    auto refInputRange(R)(R range) { return new RefInputRange!R(range); }
+
+    {
+        auto arr = [ Item(1,2), Item(1,3), Item(2,3) ];
+        static assert(isForwardRange!(typeof(arr)));
+
+        auto byX = chunkBy!(a => a.x)(arr);
+        static assert(isForwardRange!(typeof(byX)));
+
+        auto byX_subrange1 = byX.front[1].save;
+        auto byX_subrange2 = byX.front[1].save;
+        static assert(isForwardRange!(typeof(byX_subrange1)));
+        static assert(isForwardRange!(typeof(byX_subrange2)));
+
+        byX.popFront();
+        assert(byX_subrange1.equal([ Item(1,2), Item(1,3) ]));
+        byX_subrange1.popFront();
+        assert(byX_subrange1.equal([ Item(1,3) ]));
+        assert(byX_subrange2.equal([ Item(1,2), Item(1,3) ]));
+
+        auto byY = chunkBy!(a => a.y)(arr);
+        static assert(isForwardRange!(typeof(byY)));
+
+        auto byY2 = byY.save;
+        static assert(is(typeof(byY) == typeof(byY2)));
+        byY.popFront();
+        assert(byY.front[0] == 3);
+        assert(byY.front[1].equal([ Item(1,3), Item(2,3) ]));
+        assert(byY2.front[0] == 2);
+        assert(byY2.front[1].equal([ Item(1,2) ]));
+    }
+
+    // Test non-forward input ranges.
+    {
+        auto range = refInputRange([ Item(1,1), Item(1,2), Item(2,2) ]);
+        auto byX = chunkBy!(a => a.x)(range);
+        assert(byX.front[0] == 1);
+        assert(byX.front[1].equal([ Item(1,1), Item(1,2) ]));
+        byX.popFront();
+        assert(byX.front[0] == 2);
+        assert(byX.front[1].equal([ Item(2,2) ]));
+        byX.popFront();
+        assert(byX.empty);
+        assert(range.empty);
+
+        range = refInputRange([ Item(1,1), Item(1,2), Item(2,2) ]);
+        auto byY = chunkBy!(a => a.y)(range);
+        assert(byY.front[0] == 1);
+        assert(byY.front[1].equal([ Item(1,1) ]));
+        byY.popFront();
+        assert(byY.front[0] == 2);
+        assert(byY.front[1].equal([ Item(1,2), Item(2,2) ]));
+        byY.popFront();
+        assert(byY.empty);
+        assert(range.empty);
+    }
+}
+
+// Issue 13595
+version (none) // This requires support for non-equivalence relations
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    auto r = [1, 2, 3, 4, 5, 6, 7, 8, 9].chunkBy!((x, y) => ((x*y) % 3) == 0);
+    assert(r.equal!equal([
+        [1],
+        [2, 3, 4],
+        [5, 6, 7],
+        [8, 9]
+    ]));
+}
+
+// Issue 13805
+@system unittest
+{
+    [""].map!((s) => s).chunkBy!((x, y) => true);
+}
+
+// joiner
+/**
+Lazily joins a range of ranges with a separator. The separator itself
+is a range. If a separator is not provided, then the ranges are
+joined directly without anything in between them (often called `flatten`
+in other languages).
+
+Params:
+    r = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) of input
+        ranges to be joined.
+    sep = A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) of
+        element(s) to serve as separators in the joined range.
+
+Returns:
+A range of elements in the joined range. This will be a forward range if
+both outer and inner ranges of $(D RoR) are forward ranges; otherwise it will
+be only an input range.
+
+See_also:
+$(REF chain, std,range), which chains a sequence of ranges with compatible elements
+into a single range.
+ */
+auto joiner(RoR, Separator)(RoR r, Separator sep)
+if (isInputRange!RoR && isInputRange!(ElementType!RoR)
+        && isForwardRange!Separator
+        && is(ElementType!Separator : ElementType!(ElementType!RoR)))
+{
+    static struct Result
+    {
+        private RoR _items;
+        private ElementType!RoR _current;
+        private Separator _sep, _currentSep;
+
+        // This is a mixin instead of a function for the following reason (as
+        // explained by Kenji Hara): "This is necessary from 2.061.  If a
+        // struct has a nested struct member, it must be directly initialized
+        // in its constructor to avoid leaving undefined state.  If you change
+        // setItem to a function, the initialization of _current field is
+        // wrapped into private member function, then compiler could not detect
+        // that is correctly initialized while constructing.  To avoid the
+        // compiler error check, string mixin is used."
+        private enum setItem =
+        q{
+            if (!_items.empty)
+            {
+                // If we're exporting .save, we must not consume any of the
+                // subranges, since RoR.save does not guarantee that the states
+                // of the subranges are also saved.
+                static if (isForwardRange!RoR &&
+                           isForwardRange!(ElementType!RoR))
+                    _current = _items.front.save;
+                else
+                    _current = _items.front;
+            }
+        };
+
+        private void useSeparator()
+        {
+            // Separator must always come after an item.
+            assert(_currentSep.empty && !_items.empty,
+                    "joiner: internal error");
+            _items.popFront();
+
+            // If there are no more items, we're done, since separators are not
+            // terminators.
+            if (_items.empty) return;
+
+            if (_sep.empty)
+            {
+                // Advance to the next range in the
+                // input
+                while (_items.front.empty)
+                {
+                    _items.popFront();
+                    if (_items.empty) return;
+                }
+                mixin(setItem);
+            }
+            else
+            {
+                _currentSep = _sep.save;
+                assert(!_currentSep.empty);
+            }
+        }
+
+        private enum useItem =
+        q{
+            // FIXME: this will crash if either _currentSep or _current are
+            // class objects, because .init is null when the ctor invokes this
+            // mixin.
+            //assert(_currentSep.empty && _current.empty,
+            //        "joiner: internal error");
+
+            // Use the input
+            if (_items.empty) return;
+            mixin(setItem);
+            if (_current.empty)
+            {
+                // No data in the current item - toggle to use the separator
+                useSeparator();
+            }
+        };
+
+        this(RoR items, Separator sep)
+        {
+            _items = items;
+            _sep = sep;
+
+            //mixin(useItem); // _current should be initialized in place
+            if (_items.empty)
+                _current = _current.init;   // set invalid state
+            else
+            {
+                // If we're exporting .save, we must not consume any of the
+                // subranges, since RoR.save does not guarantee that the states
+                // of the subranges are also saved.
+                static if (isForwardRange!RoR &&
+                           isForwardRange!(ElementType!RoR))
+                    _current = _items.front.save;
+                else
+                    _current = _items.front;
+
+                if (_current.empty)
+                {
+                    // No data in the current item - toggle to use the separator
+                    useSeparator();
+                }
+            }
+        }
+
+        @property auto empty()
+        {
+            return _items.empty;
+        }
+
+        @property ElementType!(ElementType!RoR) front()
+        {
+            if (!_currentSep.empty) return _currentSep.front;
+            assert(!_current.empty, "Attempting to fetch the front of an empty joiner.");
+            return _current.front;
+        }
+
+        void popFront()
+        {
+            assert(!_items.empty, "Attempting to popFront an empty joiner.");
+            // Using separator?
+            if (!_currentSep.empty)
+            {
+                _currentSep.popFront();
+                if (!_currentSep.empty) return;
+                mixin(useItem);
+            }
+            else
+            {
+                // we're using the range
+                _current.popFront();
+                if (!_current.empty) return;
+                useSeparator();
+            }
+        }
+
+        static if (isForwardRange!RoR && isForwardRange!(ElementType!RoR))
+        {
+            @property auto save()
+            {
+                Result copy = this;
+                copy._items = _items.save;
+                copy._current = _current.save;
+                copy._sep = _sep.save;
+                copy._currentSep = _currentSep.save;
+                return copy;
+            }
+        }
+    }
+    return Result(r, sep);
+}
+
+///
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.conv : text;
+
+    assert(["abc", "def"].joiner.equal("abcdef"));
+    assert(["Mary", "has", "a", "little", "lamb"]
+        .joiner("...")
+        .equal("Mary...has...a...little...lamb"));
+    assert(["", "abc"].joiner("xyz").equal("xyzabc"));
+    assert([""].joiner("xyz").equal(""));
+    assert(["", ""].joiner("xyz").equal("xyz"));
+}
+
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range.interfaces;
+    import std.range.primitives;
+    // joiner() should work for non-forward ranges too.
+    auto r = inputRangeObject(["abc", "def"]);
+    assert(equal(joiner(r, "xyz"), "abcxyzdef"));
+}
+
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range;
+
+    // Related to issue 8061
+    auto r = joiner([
+        inputRangeObject("abc"),
+        inputRangeObject("def"),
+    ], "-*-");
+
+    assert(equal(r, "abc-*-def"));
+
+    // Test case where separator is specified but is empty.
+    auto s = joiner([
+        inputRangeObject("abc"),
+        inputRangeObject("def"),
+    ], "");
+
+    assert(equal(s, "abcdef"));
+
+    // Test empty separator with some empty elements
+    auto t = joiner([
+        inputRangeObject("abc"),
+        inputRangeObject(""),
+        inputRangeObject("def"),
+        inputRangeObject(""),
+    ], "");
+
+    assert(equal(t, "abcdef"));
+
+    // Test empty elements with non-empty separator
+    auto u = joiner([
+        inputRangeObject(""),
+        inputRangeObject("abc"),
+        inputRangeObject(""),
+        inputRangeObject("def"),
+        inputRangeObject(""),
+    ], "+-");
+
+    assert(equal(u, "+-abc+-+-def+-"));
+
+    // Issue 13441: only(x) as separator
+    string[][] lines = [null];
+    lines
+        .joiner(only("b"))
+        .array();
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+
+    // Transience correctness test
+    struct TransientRange
+    {
+    @safe:
+        int[][] src;
+        int[] buf;
+
+        this(int[][] _src)
+        {
+            src = _src;
+            buf.length = 100;
+        }
+        @property bool empty() { return src.empty; }
+        @property int[] front()
+        {
+            assert(src.front.length <= buf.length);
+            buf[0 .. src.front.length] = src.front[0..$];
+            return buf[0 .. src.front.length];
+        }
+        void popFront() { src.popFront(); }
+    }
+
+    // Test embedded empty elements
+    auto tr1 = TransientRange([[], [1,2,3], [], [4]]);
+    assert(equal(joiner(tr1, [0]), [0,1,2,3,0,0,4]));
+
+    // Test trailing empty elements
+    auto tr2 = TransientRange([[], [1,2,3], []]);
+    assert(equal(joiner(tr2, [0]), [0,1,2,3,0]));
+
+    // Test no empty elements
+    auto tr3 = TransientRange([[1,2], [3,4]]);
+    assert(equal(joiner(tr3, [0,1]), [1,2,0,1,3,4]));
+
+    // Test consecutive empty elements
+    auto tr4 = TransientRange([[1,2], [], [], [], [3,4]]);
+    assert(equal(joiner(tr4, [0,1]), [1,2,0,1,0,1,0,1,0,1,3,4]));
+
+    // Test consecutive trailing empty elements
+    auto tr5 = TransientRange([[1,2], [3,4], [], []]);
+    assert(equal(joiner(tr5, [0,1]), [1,2,0,1,3,4,0,1,0,1]));
+}
+
+@safe unittest
+{
+    static assert(isInputRange!(typeof(joiner([""], ""))));
+    static assert(isForwardRange!(typeof(joiner([""], ""))));
+}
+
+/// Ditto
+auto joiner(RoR)(RoR r)
+if (isInputRange!RoR && isInputRange!(ElementType!RoR))
+{
+    static struct Result
+    {
+    private:
+        RoR _items;
+        ElementType!RoR _current;
+        enum prepare =
+        q{
+            // Skip over empty subranges.
+            if (_items.empty) return;
+            while (_items.front.empty)
+            {
+                _items.popFront();
+                if (_items.empty) return;
+            }
+            // We cannot export .save method unless we ensure subranges are not
+            // consumed when a .save'd copy of ourselves is iterated over. So
+            // we need to .save each subrange we traverse.
+            static if (isForwardRange!RoR && isForwardRange!(ElementType!RoR))
+                _current = _items.front.save;
+            else
+                _current = _items.front;
+        };
+        this(RoR items, ElementType!RoR current)
+        {
+            _items = items;
+            _current = current;
+        }
+    public:
+        this(RoR r)
+        {
+            _items = r;
+            //mixin(prepare); // _current should be initialized in place
+
+            // Skip over empty subranges.
+            while (!_items.empty && _items.front.empty)
+                _items.popFront();
+
+            if (_items.empty)
+                _current = _current.init;   // set invalid state
+            else
+            {
+                // We cannot export .save method unless we ensure subranges are not
+                // consumed when a .save'd copy of ourselves is iterated over. So
+                // we need to .save each subrange we traverse.
+                static if (isForwardRange!RoR && isForwardRange!(ElementType!RoR))
+                    _current = _items.front.save;
+                else
+                    _current = _items.front;
+            }
+        }
+        static if (isInfinite!RoR)
+        {
+            enum bool empty = false;
+        }
+        else
+        {
+            @property auto empty()
+            {
+                return _items.empty;
+            }
+        }
+        @property auto ref front()
+        {
+            assert(!empty, "Attempting to fetch the front of an empty joiner.");
+            return _current.front;
+        }
+        void popFront()
+        {
+            assert(!_current.empty, "Attempting to popFront an empty joiner.");
+            _current.popFront();
+            if (_current.empty)
+            {
+                assert(!_items.empty);
+                _items.popFront();
+                mixin(prepare);
+            }
+        }
+        static if (isForwardRange!RoR && isForwardRange!(ElementType!RoR))
+        {
+            @property auto save()
+            {
+                return Result(_items.save, _current.save);
+            }
+        }
+
+        static if (hasAssignableElements!(ElementType!RoR))
+        {
+            @property void front(ElementType!(ElementType!RoR) element)
+            {
+                assert(!empty, "Attempting to assign to front of an empty joiner.");
+                _current.front = element;
+            }
+
+            @property void front(ref ElementType!(ElementType!RoR) element)
+            {
+                assert(!empty, "Attempting to assign to front of an empty joiner.");
+                _current.front = element;
+            }
+        }
+    }
+    return Result(r);
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range.interfaces : inputRangeObject;
+    import std.range : repeat;
+
+    static assert(isInputRange!(typeof(joiner([""]))));
+    static assert(isForwardRange!(typeof(joiner([""]))));
+    assert(equal(joiner([""]), ""));
+    assert(equal(joiner(["", ""]), ""));
+    assert(equal(joiner(["", "abc"]), "abc"));
+    assert(equal(joiner(["abc", ""]), "abc"));
+    assert(equal(joiner(["abc", "def"]), "abcdef"));
+    assert(equal(joiner(["Mary", "has", "a", "little", "lamb"]),
+                    "Maryhasalittlelamb"));
+    assert(equal(joiner(repeat("abc", 3)), "abcabcabc"));
+
+    // joiner allows in-place mutation!
+    auto a = [ [1, 2, 3], [42, 43] ];
+    auto j = joiner(a);
+    j.front = 44;
+    assert(a == [ [44, 2, 3], [42, 43] ]);
+    assert(equal(j, [44, 2, 3, 42, 43]));
+}
+
+
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range.interfaces : inputRangeObject;
+
+    // bugzilla 8240
+    assert(equal(joiner([inputRangeObject("")]), ""));
+
+    // issue 8792
+    auto b = [[1], [2], [3]];
+    auto jb = joiner(b);
+    auto js = jb.save;
+    assert(equal(jb, js));
+
+    auto js2 = jb.save;
+    jb.popFront();
+    assert(!equal(jb, js));
+    assert(equal(js2, js));
+    js.popFront();
+    assert(equal(jb, js));
+    assert(!equal(js2, js));
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+
+    struct TransientRange
+    {
+    @safe:
+        int[] _buf;
+        int[][] _values;
+        this(int[][] values)
+        {
+            _values = values;
+            _buf = new int[128];
+        }
+        @property bool empty()
+        {
+            return _values.length == 0;
+        }
+        @property auto front()
+        {
+            foreach (i; 0 .. _values.front.length)
+            {
+                _buf[i] = _values[0][i];
+            }
+            return _buf[0 .. _values.front.length];
+        }
+        void popFront()
+        {
+            _values = _values[1 .. $];
+        }
+    }
+
+    auto rr = TransientRange([[1,2], [3,4,5], [], [6,7]]);
+
+    // Can't use array() or equal() directly because they fail with transient
+    // .front.
+    int[] result;
+    foreach (c; rr.joiner())
+    {
+        result ~= c;
+    }
+
+    assert(equal(result, [1,2,3,4,5,6,7]));
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.algorithm.internal : algoFormat;
+
+    struct TransientRange
+    {
+    @safe:
+        dchar[] _buf;
+        dstring[] _values;
+        this(dstring[] values)
+        {
+            _buf.length = 128;
+            _values = values;
+        }
+        @property bool empty()
+        {
+            return _values.length == 0;
+        }
+        @property auto front()
+        {
+            foreach (i; 0 .. _values.front.length)
+            {
+                _buf[i] = _values[0][i];
+            }
+            return _buf[0 .. _values.front.length];
+        }
+        void popFront()
+        {
+            _values = _values[1 .. $];
+        }
+    }
+
+    auto rr = TransientRange(["abc"d, "12"d, "def"d, "34"d]);
+
+    // Can't use array() or equal() directly because they fail with transient
+    // .front.
+    dchar[] result;
+    foreach (c; rr.joiner())
+    {
+        result ~= c;
+    }
+
+    import std.conv : to;
+    assert(equal(result, "abc12def34"d),
+        //Convert to string for assert's message
+        to!string("Unexpected result: '%s'"d.algoFormat(result)));
+}
+
+// Issue 8061
+@system unittest
+{
+    import std.conv : to;
+    import std.range.interfaces;
+
+    auto r = joiner([inputRangeObject("ab"), inputRangeObject("cd")]);
+    assert(isForwardRange!(typeof(r)));
+
+    auto str = to!string(r);
+    assert(str == "abcd");
+}
+
+@safe unittest
+{
+    import std.range : repeat;
+
+    class AssignableRange
+    {
+    @safe:
+        int element;
+        @property int front()
+        {
+            return element;
+        }
+
+        enum empty = false;
+
+        void popFront()
+        {
+        }
+
+        @property void front(int newValue)
+        {
+            element = newValue;
+        }
+    }
+
+    static assert(isInputRange!AssignableRange);
+    static assert(is(ElementType!AssignableRange == int));
+    static assert(hasAssignableElements!AssignableRange);
+    static assert(!hasLvalueElements!AssignableRange);
+
+    auto range = new AssignableRange();
+    assert(range.element == 0);
+
+    auto joined = joiner(repeat(range));
+    joined.front = 5;
+    assert(range.element == 5);
+    assert(joined.front == 5);
+
+    joined.popFront;
+    int byRef = 7;
+    joined.front = byRef;
+    assert(range.element == byRef);
+    assert(joined.front == byRef);
+}
+
+/++
+Implements the homonym function (also known as $(D accumulate), $(D
+compress), $(D inject), or $(D foldl)) present in various programming
+languages of functional flavor. There is also $(LREF fold) which does
+the same thing but with the opposite parameter order.
+The call $(D reduce!(fun)(seed, range)) first assigns $(D seed) to
+an internal variable $(D result), also called the accumulator.
+Then, for each element $(D x) in $(D range), $(D result = fun(result, x))
+gets evaluated. Finally, $(D result) is returned.
+The one-argument version $(D reduce!(fun)(range))
+works similarly, but it uses the first element of the range as the
+seed (the range must be non-empty).
+
+Returns:
+    the accumulated $(D result)
+
+Params:
+    fun = one or more functions
+
+See_Also:
+    $(HTTP en.wikipedia.org/wiki/Fold_(higher-order_function), Fold (higher-order function))
+
+    $(LREF fold) is functionally equivalent to $(LREF reduce) with the argument order reversed,
+    and without the need to use $(LREF tuple) for multiple seeds. This makes it easier
+    to use in UFCS chains.
+
+    $(LREF sum) is similar to $(D reduce!((a, b) => a + b)) that offers
+    pairwise summing of floating point numbers.
++/
+template reduce(fun...)
+if (fun.length >= 1)
+{
+    import std.meta : staticMap;
+
+    alias binfuns = staticMap!(binaryFun, fun);
+    static if (fun.length > 1)
+        import std.typecons : tuple, isTuple;
+
+    /++
+    No-seed version. The first element of $(D r) is used as the seed's value.
+
+    For each function $(D f) in $(D fun), the corresponding
+    seed type $(D S) is $(D Unqual!(typeof(f(e, e)))), where $(D e) is an
+    element of $(D r): $(D ElementType!R) for ranges,
+    and $(D ForeachType!R) otherwise.
+
+    Once S has been determined, then $(D S s = e;) and $(D s = f(s, e);)
+    must both be legal.
+
+    If $(D r) is empty, an $(D Exception) is thrown.
+
+    Params:
+        r = an iterable value as defined by $(D isIterable)
+
+    Returns:
+        the final result of the accumulator applied to the iterable
+    +/
+    auto reduce(R)(R r)
+    if (isIterable!R)
+    {
+        import std.exception : enforce;
+        alias E = Select!(isInputRange!R, ElementType!R, ForeachType!R);
+        alias Args = staticMap!(ReduceSeedType!E, binfuns);
+
+        static if (isInputRange!R)
+        {
+            enforce(!r.empty, "Cannot reduce an empty input range w/o an explicit seed value.");
+            Args result = r.front;
+            r.popFront();
+            return reduceImpl!false(r, result);
+        }
+        else
+        {
+            auto result = Args.init;
+            return reduceImpl!true(r, result);
+        }
+    }
+
+    /++
+    Seed version. The seed should be a single value if $(D fun) is a
+    single function. If $(D fun) is multiple functions, then $(D seed)
+    should be a $(REF Tuple, std,typecons), with one field per function in $(D f).
+
+    For convenience, if the seed is const, or has qualified fields, then
+    $(D reduce) will operate on an unqualified copy. If this happens
+    then the returned type will not perfectly match $(D S).
+
+    Use $(D fold) instead of $(D reduce) to use the seed version in a UFCS chain.
+
+    Params:
+        seed = the initial value of the accumulator
+        r = an iterable value as defined by $(D isIterable)
+
+    Returns:
+        the final result of the accumulator applied to the iterable
+    +/
+    auto reduce(S, R)(S seed, R r)
+    if (isIterable!R)
+    {
+        static if (fun.length == 1)
+            return reducePreImpl(r, seed);
+        else
+        {
+            import std.algorithm.internal : algoFormat;
+            static assert(isTuple!S, algoFormat("Seed %s should be a Tuple", S.stringof));
+            return reducePreImpl(r, seed.expand);
+        }
+    }
+
+    private auto reducePreImpl(R, Args...)(R r, ref Args args)
+    {
+        alias Result = staticMap!(Unqual, Args);
+        static if (is(Result == Args))
+            alias result = args;
+        else
+            Result result = args;
+        return reduceImpl!false(r, result);
+    }
+
+    private auto reduceImpl(bool mustInitialize, R, Args...)(R r, ref Args args)
+    if (isIterable!R)
+    {
+        import std.algorithm.internal : algoFormat;
+        static assert(Args.length == fun.length,
+            algoFormat("Seed %s does not have the correct amount of fields (should be %s)", Args.stringof, fun.length));
+        alias E = Select!(isInputRange!R, ElementType!R, ForeachType!R);
+
+        static if (mustInitialize) bool initialized = false;
+        foreach (/+auto ref+/ E e; r) // @@@4707@@@
+        {
+            foreach (i, f; binfuns)
+            {
+                static assert(!is(typeof(f(args[i], e))) || is(typeof(args[i] = f(args[i], e))),
+                    algoFormat(
+                        "Incompatible function/seed/element: %s/%s/%s",
+                        fullyQualifiedName!f,
+                        Args[i].stringof,
+                        E.stringof
+                    )
+                );
+            }
+
+            static if (mustInitialize) if (initialized == false)
+            {
+                import std.conv : emplaceRef;
+                foreach (i, f; binfuns)
+                    emplaceRef!(Args[i])(args[i], e);
+                initialized = true;
+                continue;
+            }
+
+            foreach (i, f; binfuns)
+                args[i] = f(args[i], e);
+        }
+        static if (mustInitialize)
+        if (!initialized)
+            throw new Exception("Cannot reduce an empty iterable w/o an explicit seed value.");
+
+        static if (Args.length == 1)
+            return args[0];
+        else
+            return tuple(args);
+    }
+}
+
+/**
+Many aggregate range operations turn out to be solved with $(D reduce)
+quickly and easily. The example below illustrates $(D reduce)'s
+remarkable power and flexibility.
+*/
+@safe unittest
+{
+    import std.algorithm.comparison : max, min;
+    import std.math : approxEqual;
+    import std.range;
+
+    int[] arr = [ 1, 2, 3, 4, 5 ];
+    // Sum all elements
+    auto sum = reduce!((a,b) => a + b)(0, arr);
+    assert(sum == 15);
+
+    // Sum again, using a string predicate with "a" and "b"
+    sum = reduce!"a + b"(0, arr);
+    assert(sum == 15);
+
+    // Compute the maximum of all elements
+    auto largest = reduce!(max)(arr);
+    assert(largest == 5);
+
+    // Max again, but with Uniform Function Call Syntax (UFCS)
+    largest = arr.reduce!(max);
+    assert(largest == 5);
+
+    // Compute the number of odd elements
+    auto odds = reduce!((a,b) => a + (b & 1))(0, arr);
+    assert(odds == 3);
+
+    // Compute the sum of squares
+    auto ssquares = reduce!((a,b) => a + b * b)(0, arr);
+    assert(ssquares == 55);
+
+    // Chain multiple ranges into seed
+    int[] a = [ 3, 4 ];
+    int[] b = [ 100 ];
+    auto r = reduce!("a + b")(chain(a, b));
+    assert(r == 107);
+
+    // Mixing convertible types is fair game, too
+    double[] c = [ 2.5, 3.0 ];
+    auto r1 = reduce!("a + b")(chain(a, b, c));
+    assert(approxEqual(r1, 112.5));
+
+    // To minimize nesting of parentheses, Uniform Function Call Syntax can be used
+    auto r2 = chain(a, b, c).reduce!("a + b");
+    assert(approxEqual(r2, 112.5));
+}
+
+/**
+Sometimes it is very useful to compute multiple aggregates in one pass.
+One advantage is that the computation is faster because the looping overhead
+is shared. That's why $(D reduce) accepts multiple functions.
+If two or more functions are passed, $(D reduce) returns a
+$(REF Tuple, std,typecons) object with one member per passed-in function.
+The number of seeds must be correspondingly increased.
+*/
+@safe unittest
+{
+    import std.algorithm.comparison : max, min;
+    import std.math : approxEqual, sqrt;
+    import std.typecons : tuple, Tuple;
+
+    double[] a = [ 3.0, 4, 7, 11, 3, 2, 5 ];
+    // Compute minimum and maximum in one pass
+    auto r = reduce!(min, max)(a);
+    // The type of r is Tuple!(int, int)
+    assert(approxEqual(r[0], 2));  // minimum
+    assert(approxEqual(r[1], 11)); // maximum
+
+    // Compute sum and sum of squares in one pass
+    r = reduce!("a + b", "a + b * b")(tuple(0.0, 0.0), a);
+    assert(approxEqual(r[0], 35));  // sum
+    assert(approxEqual(r[1], 233)); // sum of squares
+    // Compute average and standard deviation from the above
+    auto avg = r[0] / a.length;
+    assert(avg == 5);
+    auto stdev = sqrt(r[1] / a.length - avg * avg);
+    assert(cast(int) stdev == 2);
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : max, min;
+    import std.range : chain;
+    import std.typecons : tuple, Tuple;
+
+    double[] a = [ 3, 4 ];
+    auto r = reduce!("a + b")(0.0, a);
+    assert(r == 7);
+    r = reduce!("a + b")(a);
+    assert(r == 7);
+    r = reduce!(min)(a);
+    assert(r == 3);
+    double[] b = [ 100 ];
+    auto r1 = reduce!("a + b")(chain(a, b));
+    assert(r1 == 107);
+
+    // two funs
+    auto r2 = reduce!("a + b", "a - b")(tuple(0.0, 0.0), a);
+    assert(r2[0] == 7 && r2[1] == -7);
+    auto r3 = reduce!("a + b", "a - b")(a);
+    assert(r3[0] == 7 && r3[1] == -1);
+
+    a = [ 1, 2, 3, 4, 5 ];
+    // Stringize with commas
+    string rep = reduce!("a ~ `, ` ~ to!(string)(b)")("", a);
+    assert(rep[2 .. $] == "1, 2, 3, 4, 5", "["~rep[2 .. $]~"]");
+}
+
+@system unittest
+{
+    import std.algorithm.comparison : max, min;
+    import std.exception : assertThrown;
+    import std.range : iota;
+    import std.typecons : tuple, Tuple;
+
+    // Test the opApply case.
+    static struct OpApply
+    {
+        bool actEmpty;
+
+        int opApply(scope int delegate(ref int) dg)
+        {
+            int res;
+            if (actEmpty) return res;
+
+            foreach (i; 0 .. 100)
+            {
+                res = dg(i);
+                if (res) break;
+            }
+            return res;
+        }
+    }
+
+    OpApply oa;
+    auto hundredSum = reduce!"a + b"(iota(100));
+    assert(reduce!"a + b"(5, oa) == hundredSum + 5);
+    assert(reduce!"a + b"(oa) == hundredSum);
+    assert(reduce!("a + b", max)(oa) == tuple(hundredSum, 99));
+    assert(reduce!("a + b", max)(tuple(5, 0), oa) == tuple(hundredSum + 5, 99));
+
+    // Test for throwing on empty range plus no seed.
+    assertThrown(reduce!"a + b"([1, 2][0 .. 0]));
+
+    oa.actEmpty = true;
+    assertThrown(reduce!"a + b"(oa));
+}
+
+@safe unittest
+{
+    const float a = 0.0;
+    const float[] b = [ 1.2, 3, 3.3 ];
+    float[] c = [ 1.2, 3, 3.3 ];
+    auto r = reduce!"a + b"(a, b);
+    r = reduce!"a + b"(a, c);
+    assert(r == 7.5);
+}
+
+@safe unittest
+{
+    // Issue #10408 - Two-function reduce of a const array.
+    import std.algorithm.comparison : max, min;
+    import std.typecons : tuple, Tuple;
+
+    const numbers = [10, 30, 20];
+    immutable m = reduce!(min)(numbers);
+    assert(m == 10);
+    immutable minmax = reduce!(min, max)(numbers);
+    assert(minmax == tuple(10, 30));
+}
+
+@safe unittest
+{
+    //10709
+    import std.typecons : tuple, Tuple;
+
+    enum foo = "a + 0.5 * b";
+    auto r = [0, 1, 2, 3];
+    auto r1 = reduce!foo(r);
+    auto r2 = reduce!(foo, foo)(r);
+    assert(r1 == 3);
+    assert(r2 == tuple(3, 3));
+}
+
+@system unittest
+{
+    static struct OpApply
+    {
+        int opApply(int delegate(ref int) dg)
+        {
+            int[] a = [1, 2, 3];
+
+            int res = 0;
+            foreach (ref e; a)
+            {
+                res = dg(e);
+                if (res) break;
+            }
+            return res;
+        }
+    }
+    //test CTFE and functions with context
+    int fun(int a, int b) @safe {return a + b + 1;}
+    auto foo()
+    {
+        import std.algorithm.comparison : max;
+        import std.typecons : tuple, Tuple;
+
+        auto a = reduce!(fun)([1, 2, 3]);
+        auto b = reduce!(fun, fun)([1, 2, 3]);
+        auto c = reduce!(fun)(0, [1, 2, 3]);
+        auto d = reduce!(fun, fun)(tuple(0, 0), [1, 2, 3]);
+        auto e = reduce!(fun)(0, OpApply());
+        auto f = reduce!(fun, fun)(tuple(0, 0), OpApply());
+
+        return max(a, b.expand, c, d.expand, e, f.expand);
+    }
+    auto a = foo();
+    assert(a == 9);
+    enum b = foo();
+    assert(b == 9);
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : max, min;
+    import std.typecons : tuple, Tuple;
+
+    //http://forum.dlang.org/post/oghtttkopzjshsuflelk@forum.dlang.org
+    //Seed is tuple of const.
+    static auto minmaxElement(alias F = min, alias G = max, R)(in R range)
+    @safe pure nothrow
+    if (isInputRange!R)
+    {
+        return reduce!(F, G)(tuple(ElementType!R.max,
+                                   ElementType!R.min), range);
+    }
+    assert(minmaxElement([1, 2, 3]) == tuple(1, 3));
+}
+
+@safe unittest //12569
+{
+    import std.algorithm.comparison : max, min;
+    import std.typecons : tuple;
+    dchar c = 'a';
+    reduce!(min, max)(tuple(c, c), "hello"); // OK
+    static assert(!is(typeof(reduce!(min, max)(tuple(c), "hello"))));
+    static assert(!is(typeof(reduce!(min, max)(tuple(c, c, c), "hello"))));
+
+
+    //"Seed dchar should be a Tuple"
+    static assert(!is(typeof(reduce!(min, max)(c, "hello"))));
+    //"Seed (dchar) does not have the correct amount of fields (should be 2)"
+    static assert(!is(typeof(reduce!(min, max)(tuple(c), "hello"))));
+    //"Seed (dchar, dchar, dchar) does not have the correct amount of fields (should be 2)"
+    static assert(!is(typeof(reduce!(min, max)(tuple(c, c, c), "hello"))));
+    //"Incompatable function/seed/element: all(alias pred = "a")/int/dchar"
+    static assert(!is(typeof(reduce!all(1, "hello"))));
+    static assert(!is(typeof(reduce!(all, all)(tuple(1, 1), "hello"))));
+}
+
+@safe unittest //13304
+{
+    int[] data;
+    static assert(is(typeof(reduce!((a, b) => a + b)(data))));
+    assert(data.length == 0);
+}
+
+//Helper for Reduce
+private template ReduceSeedType(E)
+{
+    static template ReduceSeedType(alias fun)
+    {
+        import std.algorithm.internal : algoFormat;
+
+        alias ReduceSeedType = Unqual!(typeof(fun(lvalueOf!E, lvalueOf!E)));
+
+        //Check the Seed type is useable.
+        ReduceSeedType s = ReduceSeedType.init;
+        static assert(is(typeof({ReduceSeedType s = lvalueOf!E;})) &&
+            is(typeof(lvalueOf!ReduceSeedType = fun(lvalueOf!ReduceSeedType, lvalueOf!E))),
+            algoFormat(
+                "Unable to deduce an acceptable seed type for %s with element type %s.",
+                fullyQualifiedName!fun,
+                E.stringof
+            )
+        );
+    }
+}
+
+
+/++
+Implements the homonym function (also known as $(D accumulate), $(D
+compress), $(D inject), or $(D foldl)) present in various programming
+languages of functional flavor. The call $(D fold!(fun)(range, seed))
+first assigns $(D seed) to an internal variable $(D result),
+also called the accumulator. Then, for each element $(D x) in $(D
+range), $(D result = fun(result, x)) gets evaluated. Finally, $(D
+result) is returned. The one-argument version $(D fold!(fun)(range))
+works similarly, but it uses the first element of the range as the
+seed (the range must be non-empty).
+
+Returns:
+    the accumulated $(D result)
+
+See_Also:
+    $(HTTP en.wikipedia.org/wiki/Fold_(higher-order_function), Fold (higher-order function))
+
+    $(LREF sum) is similar to $(D fold!((a, b) => a + b)) that offers
+    precise summing of floating point numbers.
+
+    This is functionally equivalent to $(LREF reduce) with the argument order reversed,
+    and without the need to use $(LREF tuple) for multiple seeds.
++/
+template fold(fun...)
+if (fun.length >= 1)
+{
+    auto fold(R, S...)(R r, S seed)
+    {
+        static if (S.length < 2)
+        {
+            return reduce!fun(seed, r);
+        }
+        else
+        {
+            import std.typecons : tuple;
+            return reduce!fun(tuple(seed), r);
+        }
+    }
+}
+
+///
+@safe pure unittest
+{
+    immutable arr = [1, 2, 3, 4, 5];
+
+    // Sum all elements
+    assert(arr.fold!((a, b) => a + b) == 15);
+
+    // Sum all elements with explicit seed
+    assert(arr.fold!((a, b) => a + b)(6) == 21);
+
+    import std.algorithm.comparison : min, max;
+    import std.typecons : tuple;
+
+    // Compute minimum and maximum at the same time
+    assert(arr.fold!(min, max) == tuple(1, 5));
+
+    // Compute minimum and maximum at the same time with seeds
+    assert(arr.fold!(min, max)(0, 7) == tuple(0, 7));
+
+    // Can be used in a UFCS chain
+    assert(arr.map!(a => a + 1).fold!((a, b) => a + b) == 20);
+
+    // Return the last element of any range
+    assert(arr.fold!((a, b) => b) == 5);
+}
+
+@safe @nogc pure nothrow unittest
+{
+    int[1] arr;
+    static assert(!is(typeof(arr.fold!())));
+    static assert(!is(typeof(arr.fold!(a => a))));
+    static assert(is(typeof(arr.fold!((a, b) => a))));
+    static assert(is(typeof(arr.fold!((a, b) => a)(1))));
+    assert(arr.length == 1);
+}
+
+/++
+Similar to `fold`, but returns a range containing the successive reduced values.
+The call $(D cumulativeFold!(fun)(range, seed)) first assigns `seed` to an
+internal variable `result`, also called the accumulator.
+The returned range contains the values $(D result = fun(result, x)) lazily
+evaluated for each element `x` in `range`. Finally, the last element has the
+same value as $(D fold!(fun)(seed, range)).
+The one-argument version $(D cumulativeFold!(fun)(range)) works similarly, but
+it returns the first element unchanged and uses it as seed for the next
+elements.
+This function is also known as
+    $(HTTP en.cppreference.com/w/cpp/algorithm/partial_sum, partial_sum),
+    $(HTTP docs.python.org/3/library/itertools.html#itertools.accumulate, accumulate),
+    $(HTTP hackage.haskell.org/package/base-4.8.2.0/docs/Prelude.html#v:scanl, scan),
+    $(HTTP mathworld.wolfram.com/CumulativeSum.html, Cumulative Sum).
+
+Params:
+    fun = one or more functions to use as fold operation
+
+Returns:
+    The function returns a range containing the consecutive reduced values. If
+    there is more than one `fun`, the element type will be $(REF Tuple,
+    std,typecons) containing one element for each `fun`.
+
+See_Also:
+    $(HTTP en.wikipedia.org/wiki/Prefix_sum, Prefix Sum)
++/
+template cumulativeFold(fun...)
+if (fun.length >= 1)
+{
+    import std.meta : staticMap;
+    private alias binfuns = staticMap!(binaryFun, fun);
+
+    /++
+    No-seed version. The first element of `r` is used as the seed's value.
+    For each function `f` in `fun`, the corresponding seed type `S` is
+    $(D Unqual!(typeof(f(e, e)))), where `e` is an element of `r`:
+    `ElementType!R`.
+    Once `S` has been determined, then $(D S s = e;) and $(D s = f(s, e);) must
+    both be legal.
+
+    Params:
+        range = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
+    Returns:
+        a range containing the consecutive reduced values.
+    +/
+    auto cumulativeFold(R)(R range)
+    if (isInputRange!(Unqual!R))
+    {
+        return cumulativeFoldImpl(range);
+    }
+
+    /++
+    Seed version. The seed should be a single value if `fun` is a single
+    function. If `fun` is multiple functions, then `seed` should be a
+    $(REF Tuple, std,typecons), with one field per function in `f`.
+    For convenience, if the seed is `const`, or has qualified fields, then
+    `cumulativeFold` will operate on an unqualified copy. If this happens
+    then the returned type will not perfectly match `S`.
+
+    Params:
+        range = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
+        seed = the initial value of the accumulator
+    Returns:
+        a range containing the consecutive reduced values.
+    +/
+    auto cumulativeFold(R, S)(R range, S seed)
+    if (isInputRange!(Unqual!R))
+    {
+        static if (fun.length == 1)
+            return cumulativeFoldImpl(range, seed);
+        else
+            return cumulativeFoldImpl(range, seed.expand);
+    }
+
+    private auto cumulativeFoldImpl(R, Args...)(R range, ref Args args)
+    {
+        import std.algorithm.internal : algoFormat;
+
+        static assert(Args.length == 0 || Args.length == fun.length,
+            algoFormat("Seed %s does not have the correct amount of fields (should be %s)",
+                Args.stringof, fun.length));
+
+        static if (args.length)
+            alias State = staticMap!(Unqual, Args);
+        else
+            alias State = staticMap!(ReduceSeedType!(ElementType!R), binfuns);
+
+        foreach (i, f; binfuns)
+        {
+            static assert(!__traits(compiles, f(args[i], e)) || __traits(compiles,
+                    { args[i] = f(args[i], e); }()),
+                algoFormat("Incompatible function/seed/element: %s/%s/%s",
+                    fullyQualifiedName!f, Args[i].stringof, E.stringof));
+        }
+
+        static struct Result
+        {
+        private:
+            R source;
+            State state;
+
+            this(R range, ref Args args)
+            {
+                source = range;
+                if (source.empty)
+                    return;
+
+                foreach (i, f; binfuns)
+                {
+                    static if (args.length)
+                        state[i] = f(args[i], source.front);
+                    else
+                        state[i] = source.front;
+                }
+            }
+
+        public:
+            @property bool empty()
+            {
+                return source.empty;
+            }
+
+            @property auto front()
+            {
+                assert(!empty, "Attempting to fetch the front of an empty cumulativeFold.");
+                static if (fun.length > 1)
+                {
+                    import std.typecons : tuple;
+                    return tuple(state);
+                }
+                else
+                {
+                    return state[0];
+                }
+            }
+
+            void popFront()
+            {
+                assert(!empty, "Attempting to popFront an empty cumulativeFold.");
+                source.popFront;
+
+                if (source.empty)
+                    return;
+
+                foreach (i, f; binfuns)
+                    state[i] = f(state[i], source.front);
+            }
+
+            static if (isForwardRange!R)
+            {
+                @property auto save()
+                {
+                    auto result = this;
+                    result.source = source.save;
+                    return result;
+                }
+            }
+
+            static if (hasLength!R)
+            {
+                @property size_t length()
+                {
+                    return source.length;
+                }
+            }
+        }
+
+        return Result(range, args);
+    }
+}
+
+///
+@safe unittest
+{
+    import std.algorithm.comparison : max, min;
+    import std.array : array;
+    import std.math : approxEqual;
+    import std.range : chain;
+
+    int[] arr = [1, 2, 3, 4, 5];
+    // Partial sum of all elements
+    auto sum = cumulativeFold!((a, b) => a + b)(arr, 0);
+    assert(sum.array == [1, 3, 6, 10, 15]);
+
+    // Partial sum again, using a string predicate with "a" and "b"
+    auto sum2 = cumulativeFold!"a + b"(arr, 0);
+    assert(sum2.array == [1, 3, 6, 10, 15]);
+
+    // Compute the partial maximum of all elements
+    auto largest = cumulativeFold!max(arr);
+    assert(largest.array == [1, 2, 3, 4, 5]);
+
+    // Partial max again, but with Uniform Function Call Syntax (UFCS)
+    largest = arr.cumulativeFold!max;
+    assert(largest.array == [1, 2, 3, 4, 5]);
+
+    // Partial count of odd elements
+    auto odds = arr.cumulativeFold!((a, b) => a + (b & 1))(0);
+    assert(odds.array == [1, 1, 2, 2, 3]);
+
+    // Compute the partial sum of squares
+    auto ssquares = arr.cumulativeFold!((a, b) => a + b * b)(0);
+    assert(ssquares.array == [1, 5, 14, 30, 55]);
+
+    // Chain multiple ranges into seed
+    int[] a = [3, 4];
+    int[] b = [100];
+    auto r = cumulativeFold!"a + b"(chain(a, b));
+    assert(r.array == [3, 7, 107]);
+
+    // Mixing convertible types is fair game, too
+    double[] c = [2.5, 3.0];
+    auto r1 = cumulativeFold!"a + b"(chain(a, b, c));
+    assert(approxEqual(r1, [3, 7, 107, 109.5, 112.5]));
+
+    // To minimize nesting of parentheses, Uniform Function Call Syntax can be used
+    auto r2 = chain(a, b, c).cumulativeFold!"a + b";
+    assert(approxEqual(r2, [3, 7, 107, 109.5, 112.5]));
+}
+
+/**
+Sometimes it is very useful to compute multiple aggregates in one pass.
+One advantage is that the computation is faster because the looping overhead
+is shared. That's why `cumulativeFold` accepts multiple functions.
+If two or more functions are passed, `cumulativeFold` returns a $(REF Tuple,
+std,typecons) object with one member per passed-in function.
+The number of seeds must be correspondingly increased.
+*/
+@safe unittest
+{
+    import std.algorithm.comparison : max, min;
+    import std.algorithm.iteration : map;
+    import std.math : approxEqual;
+    import std.typecons : tuple;
+
+    double[] a = [3.0, 4, 7, 11, 3, 2, 5];
+    // Compute minimum and maximum in one pass
+    auto r = a.cumulativeFold!(min, max);
+    // The type of r is Tuple!(int, int)
+    assert(approxEqual(r.map!"a[0]", [3, 3, 3, 3, 3, 2, 2]));     // minimum
+    assert(approxEqual(r.map!"a[1]", [3, 4, 7, 11, 11, 11, 11])); // maximum
+
+    // Compute sum and sum of squares in one pass
+    auto r2 = a.cumulativeFold!("a + b", "a + b * b")(tuple(0.0, 0.0));
+    assert(approxEqual(r2.map!"a[0]", [3, 7, 14, 25, 28, 30, 35]));      // sum
+    assert(approxEqual(r2.map!"a[1]", [9, 25, 74, 195, 204, 208, 233])); // sum of squares
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal, max, min;
+    import std.conv : to;
+    import std.range : chain;
+    import std.typecons : tuple;
+
+    double[] a = [3, 4];
+    auto r = a.cumulativeFold!("a + b")(0.0);
+    assert(r.equal([3, 7]));
+    auto r2 = cumulativeFold!("a + b")(a);
+    assert(r2.equal([3, 7]));
+    auto r3 = cumulativeFold!(min)(a);
+    assert(r3.equal([3, 3]));
+    double[] b = [100];
+    auto r4 = cumulativeFold!("a + b")(chain(a, b));
+    assert(r4.equal([3, 7, 107]));
+
+    // two funs
+    auto r5 = cumulativeFold!("a + b", "a - b")(a, tuple(0.0, 0.0));
+    assert(r5.equal([tuple(3, -3), tuple(7, -7)]));
+    auto r6 = cumulativeFold!("a + b", "a - b")(a);
+    assert(r6.equal([tuple(3, 3), tuple(7, -1)]));
+
+    a = [1, 2, 3, 4, 5];
+    // Stringize with commas
+    auto rep = cumulativeFold!("a ~ `, ` ~ to!string(b)")(a, "");
+    assert(rep.map!"a[2 .. $]".equal(["1", "1, 2", "1, 2, 3", "1, 2, 3, 4", "1, 2, 3, 4, 5"]));
+
+    // Test for empty range
+    a = [];
+    assert(a.cumulativeFold!"a + b".empty);
+    assert(a.cumulativeFold!"a + b"(2.0).empty);
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : max, min;
+    import std.array : array;
+    import std.math : approxEqual;
+    import std.typecons : tuple;
+
+    const float a = 0.0;
+    const float[] b = [1.2, 3, 3.3];
+    float[] c = [1.2, 3, 3.3];
+
+    auto r = cumulativeFold!"a + b"(b, a);
+    assert(approxEqual(r, [1.2, 4.2, 7.5]));
+
+    auto r2 = cumulativeFold!"a + b"(c, a);
+    assert(approxEqual(r2, [1.2, 4.2, 7.5]));
+
+    const numbers = [10, 30, 20];
+    enum m = numbers.cumulativeFold!(min).array;
+    assert(m == [10, 10, 10]);
+    enum minmax = numbers.cumulativeFold!(min, max).array;
+    assert(minmax == [tuple(10, 10), tuple(10, 30), tuple(10, 30)]);
+}
+
+@safe unittest
+{
+    import std.math : approxEqual;
+    import std.typecons : tuple;
+
+    enum foo = "a + 0.5 * b";
+    auto r = [0, 1, 2, 3];
+    auto r1 = r.cumulativeFold!foo;
+    auto r2 = r.cumulativeFold!(foo, foo);
+    assert(approxEqual(r1, [0, 0.5, 1.5, 3]));
+    assert(approxEqual(r2.map!"a[0]", [0, 0.5, 1.5, 3]));
+    assert(approxEqual(r2.map!"a[1]", [0, 0.5, 1.5, 3]));
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal, max, min;
+    import std.array : array;
+    import std.typecons : tuple;
+
+    //Seed is tuple of const.
+    static auto minmaxElement(alias F = min, alias G = max, R)(in R range)
+    @safe pure nothrow
+    if (isInputRange!R)
+    {
+        return range.cumulativeFold!(F, G)(tuple(ElementType!R.max, ElementType!R.min));
+    }
+
+    assert(minmaxElement([1, 2, 3]).equal([tuple(1, 1), tuple(1, 2), tuple(1, 3)]));
+}
+
+@safe unittest //12569
+{
+    import std.algorithm.comparison : equal, max, min;
+    import std.typecons : tuple;
+
+    dchar c = 'a';
+
+    assert(cumulativeFold!(min, max)("hello", tuple(c, c)).equal([tuple('a', 'h'),
+        tuple('a', 'h'), tuple('a', 'l'), tuple('a', 'l'), tuple('a', 'o')]));
+    static assert(!__traits(compiles, cumulativeFold!(min, max)("hello", tuple(c))));
+    static assert(!__traits(compiles, cumulativeFold!(min, max)("hello", tuple(c, c, c))));
+
+    //"Seed dchar should be a Tuple"
+    static assert(!__traits(compiles, cumulativeFold!(min, max)("hello", c)));
+    //"Seed (dchar) does not have the correct amount of fields (should be 2)"
+    static assert(!__traits(compiles, cumulativeFold!(min, max)("hello", tuple(c))));
+    //"Seed (dchar, dchar, dchar) does not have the correct amount of fields (should be 2)"
+    static assert(!__traits(compiles, cumulativeFold!(min, max)("hello", tuple(c, c, c))));
+    //"Incompatable function/seed/element: all(alias pred = "a")/int/dchar"
+    static assert(!__traits(compiles, cumulativeFold!all("hello", 1)));
+    static assert(!__traits(compiles, cumulativeFold!(all, all)("hello", tuple(1, 1))));
+}
+
+@safe unittest //13304
+{
+    int[] data;
+    assert(data.cumulativeFold!((a, b) => a + b).empty);
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.internal.test.dummyrange : AllDummyRanges, propagatesLength,
+        propagatesRangeType, RangeType;
+
+    foreach (DummyType; AllDummyRanges)
+    {
+        DummyType d;
+        auto m = d.cumulativeFold!"a * b";
+
+        static assert(propagatesLength!(typeof(m), DummyType));
+        static if (DummyType.rt <= RangeType.Forward)
+            static assert(propagatesRangeType!(typeof(m), DummyType));
+
+        assert(m.equal([1, 2, 6, 24, 120, 720, 5040, 40_320, 362_880, 3_628_800]));
+    }
+}
+
+// splitter
+/**
+Lazily splits a range using an element as a separator. This can be used with
+any narrow string type or sliceable range type, but is most popular with string
+types.
+
+Two adjacent separators are considered to surround an empty element in
+the split range. Use $(D filter!(a => !a.empty)) on the result to compress
+empty elements.
+
+The predicate is passed to $(REF binaryFun, std,functional), and can either accept
+a string, or any callable that can be executed via $(D pred(element, s)).
+
+If the empty range is given, the result is a range with one empty
+element. If a range with one separator is given, the result is a range
+with two empty elements.
+
+If splitting a string on whitespace and token compression is desired,
+consider using $(D splitter) without specifying a separator (see fourth overload
+below).
+
+Params:
+    pred = The predicate for comparing each element with the separator,
+        defaulting to $(D "a == b").
+    r = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to be
+        split. Must support slicing and $(D .length).
+    s = The element to be treated as the separator between range segments to be
+        split.
+
+Constraints:
+    The predicate $(D pred) needs to accept an element of $(D r) and the
+    separator $(D s).
+
+Returns:
+    An input range of the subranges of elements between separators. If $(D r)
+    is a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
+    or $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives),
+    the returned range will be likewise.
+
+See_Also:
+ $(REF _splitter, std,regex) for a version that splits using a regular
+expression defined separator.
+*/
+auto splitter(alias pred = "a == b", Range, Separator)(Range r, Separator s)
+if (is(typeof(binaryFun!pred(r.front, s)) : bool)
+        && ((hasSlicing!Range && hasLength!Range) || isNarrowString!Range))
+{
+    import std.algorithm.searching : find;
+    import std.conv : unsigned;
+
+    static struct Result
+    {
+    private:
+        Range _input;
+        Separator _separator;
+        // Do we need hasLength!Range? popFront uses _input.length...
+        enum size_t _unComputed = size_t.max - 1, _atEnd = size_t.max;
+        size_t _frontLength = _unComputed;
+        size_t _backLength = _unComputed;
+
+        static if (isNarrowString!Range)
+        {
+            size_t _separatorLength;
+        }
+        else
+        {
+            enum _separatorLength = 1;
+        }
+
+        static if (isBidirectionalRange!Range)
+        {
+            static size_t lastIndexOf(Range haystack, Separator needle)
+            {
+                import std.range : retro;
+                auto r = haystack.retro().find!pred(needle);
+                return r.retro().length - 1;
+            }
+        }
+
+    public:
+        this(Range input, Separator separator)
+        {
+            _input = input;
+            _separator = separator;
+
+            static if (isNarrowString!Range)
+            {
+                import std.utf : codeLength;
+
+                _separatorLength = codeLength!(ElementEncodingType!Range)(separator);
+            }
+            if (_input.empty)
+                _frontLength = _atEnd;
+        }
+
+        static if (isInfinite!Range)
+        {
+            enum bool empty = false;
+        }
+        else
+        {
+            @property bool empty()
+            {
+                return _frontLength == _atEnd;
+            }
+        }
+
+        @property Range front()
+        {
+            assert(!empty, "Attempting to fetch the front of an empty splitter.");
+            if (_frontLength == _unComputed)
+            {
+                auto r = _input.find!pred(_separator);
+                _frontLength = _input.length - r.length;
+            }
+            return _input[0 .. _frontLength];
+        }
+
+        void popFront()
+        {
+            assert(!empty, "Attempting to popFront an empty splitter.");
+            if (_frontLength == _unComputed)
+            {
+                front;
+            }
+            assert(_frontLength <= _input.length);
+            if (_frontLength == _input.length)
+            {
+                // no more input and need to fetch => done
+                _frontLength = _atEnd;
+
+                // Probably don't need this, but just for consistency:
+                _backLength = _atEnd;
+            }
+            else
+            {
+                _input = _input[_frontLength + _separatorLength .. _input.length];
+                _frontLength = _unComputed;
+            }
+        }
+
+        static if (isForwardRange!Range)
+        {
+            @property typeof(this) save()
+            {
+                auto ret = this;
+                ret._input = _input.save;
+                return ret;
+            }
+        }
+
+        static if (isBidirectionalRange!Range)
+        {
+            @property Range back()
+            {
+                assert(!empty, "Attempting to fetch the back of an empty splitter.");
+                if (_backLength == _unComputed)
+                {
+                    immutable lastIndex = lastIndexOf(_input, _separator);
+                    if (lastIndex == -1)
+                    {
+                        _backLength = _input.length;
+                    }
+                    else
+                    {
+                        _backLength = _input.length - lastIndex - 1;
+                    }
+                }
+                return _input[_input.length - _backLength .. _input.length];
+            }
+
+            void popBack()
+            {
+                assert(!empty, "Attempting to popBack an empty splitter.");
+                if (_backLength == _unComputed)
+                {
+                    // evaluate back to make sure it's computed
+                    back;
+                }
+                assert(_backLength <= _input.length);
+                if (_backLength == _input.length)
+                {
+                    // no more input and need to fetch => done
+                    _frontLength = _atEnd;
+                    _backLength = _atEnd;
+                }
+                else
+                {
+                    _input = _input[0 .. _input.length - _backLength - _separatorLength];
+                    _backLength = _unComputed;
+                }
+            }
+        }
+    }
+
+    return Result(r, s);
+}
+
+///
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+
+    assert(equal(splitter("hello  world", ' '), [ "hello", "", "world" ]));
+    int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ];
+    int[][] w = [ [1, 2], [], [3], [4, 5], [] ];
+    assert(equal(splitter(a, 0), w));
+    a = [ 0 ];
+    assert(equal(splitter(a, 0), [ (int[]).init, (int[]).init ]));
+    a = [ 0, 1 ];
+    assert(equal(splitter(a, 0), [ [], [1] ]));
+    w = [ [0], [1], [2] ];
+    assert(equal(splitter!"a.front == b"(w, 1), [ [[0]], [[2]] ]));
+}
+
+@safe unittest
+{
+    import std.algorithm;
+    import std.array : array;
+    import std.internal.test.dummyrange;
+    import std.range : retro;
+
+    assert(equal(splitter("hello  world", ' '), [ "hello", "", "world" ]));
+    assert(equal(splitter("žlutoučkýřkůň", 'ř'), [ "žlutoučký", "kůň" ]));
+    int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ];
+    int[][] w = [ [1, 2], [], [3], [4, 5], [] ];
+    static assert(isForwardRange!(typeof(splitter(a, 0))));
+
+    assert(equal(splitter(a, 0), w));
+    a = null;
+    assert(equal(splitter(a, 0),  (int[][]).init));
+    a = [ 0 ];
+    assert(equal(splitter(a, 0), [ (int[]).init, (int[]).init ][]));
+    a = [ 0, 1 ];
+    assert(equal(splitter(a, 0), [ [], [1] ][]));
+
+    // Thoroughly exercise the bidirectional stuff.
+    auto str = "abc abcd abcde ab abcdefg abcdefghij ab ac ar an at ada";
+    assert(equal(
+        retro(splitter(str, 'a')),
+        retro(array(splitter(str, 'a')))
+    ));
+
+    // Test interleaving front and back.
+    auto split = splitter(str, 'a');
+    assert(split.front == "");
+    assert(split.back == "");
+    split.popBack();
+    assert(split.back == "d");
+    split.popFront();
+    assert(split.front == "bc ");
+    assert(split.back == "d");
+    split.popFront();
+    split.popBack();
+    assert(split.back == "t ");
+    split.popBack();
+    split.popBack();
+    split.popFront();
+    split.popFront();
+    assert(split.front == "b ");
+    assert(split.back == "r ");
+
+    foreach (DummyType; AllDummyRanges) {  // Bug 4408
+        static if (isRandomAccessRange!DummyType)
+        {
+            static assert(isBidirectionalRange!DummyType);
+            DummyType d;
+            auto s = splitter(d, 5);
+            assert(equal(s.front, [1,2,3,4]));
+            assert(equal(s.back, [6,7,8,9,10]));
+
+            auto s2 = splitter(d, [4, 5]);
+            assert(equal(s2.front, [1,2,3]));
+        }
+    }
+}
+@safe unittest
+{
+    import std.algorithm;
+    import std.range;
+    auto L = retro(iota(1L, 10L));
+    auto s = splitter(L, 5L);
+    assert(equal(s.front, [9L, 8L, 7L, 6L]));
+    s.popFront();
+    assert(equal(s.front, [4L, 3L, 2L, 1L]));
+    s.popFront();
+    assert(s.empty);
+}
+
+/**
+Similar to the previous overload of $(D splitter), except this one uses another
+range as a separator. This can be used with any narrow string type or sliceable
+range type, but is most popular with string types. The predicate is passed to
+$(REF binaryFun, std,functional), and can either accept a string, or any callable
+that can be executed via $(D pred(r.front, s.front)).
+
+Two adjacent separators are considered to surround an empty element in
+the split range. Use $(D filter!(a => !a.empty)) on the result to compress
+empty elements.
+
+Params:
+    pred = The predicate for comparing each element with the separator,
+        defaulting to $(D "a == b").
+    r = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to be
+        split.
+    s = The $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) to
+        be treated as the separator between segments of $(D r) to be split.
+
+Constraints:
+    The predicate $(D pred) needs to accept an element of $(D r) and an
+    element of $(D s).
+
+Returns:
+    An input range of the subranges of elements between separators. If $(D r)
+    is a forward range or $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives),
+    the returned range will be likewise.
+
+See_Also: $(REF _splitter, std,regex) for a version that splits using a regular
+expression defined separator.
+ */
+auto splitter(alias pred = "a == b", Range, Separator)(Range r, Separator s)
+if (is(typeof(binaryFun!pred(r.front, s.front)) : bool)
+        && (hasSlicing!Range || isNarrowString!Range)
+        && isForwardRange!Separator
+        && (hasLength!Separator || isNarrowString!Separator))
+{
+    import std.algorithm.searching : find;
+    import std.conv : unsigned;
+
+    static struct Result
+    {
+    private:
+        Range _input;
+        Separator _separator;
+        // _frontLength == size_t.max means empty
+        size_t _frontLength = size_t.max;
+        static if (isBidirectionalRange!Range)
+            size_t _backLength = size_t.max;
+
+        @property auto separatorLength() { return _separator.length; }
+
+        void ensureFrontLength()
+        {
+            if (_frontLength != _frontLength.max) return;
+            assert(!_input.empty);
+            // compute front length
+            _frontLength = (_separator.empty) ? 1 :
+                           _input.length - find!pred(_input, _separator).length;
+            static if (isBidirectionalRange!Range)
+                if (_frontLength == _input.length) _backLength = _frontLength;
+        }
+
+        void ensureBackLength()
+        {
+            static if (isBidirectionalRange!Range)
+                if (_backLength != _backLength.max) return;
+            assert(!_input.empty);
+            // compute back length
+            static if (isBidirectionalRange!Range && isBidirectionalRange!Separator)
+            {
+                import std.range : retro;
+                _backLength = _input.length -
+                    find!pred(retro(_input), retro(_separator)).source.length;
+            }
+        }
+
+    public:
+        this(Range input, Separator separator)
+        {
+            _input = input;
+            _separator = separator;
+        }
+
+        @property Range front()
+        {
+            assert(!empty, "Attempting to fetch the front of an empty splitter.");
+            ensureFrontLength();
+            return _input[0 .. _frontLength];
+        }
+
+        static if (isInfinite!Range)
+        {
+            enum bool empty = false;  // Propagate infiniteness
+        }
+        else
+        {
+            @property bool empty()
+            {
+                return _frontLength == size_t.max && _input.empty;
+            }
+        }
+
+        void popFront()
+        {
+            assert(!empty, "Attempting to popFront an empty splitter.");
+            ensureFrontLength();
+            if (_frontLength == _input.length)
+            {
+                // done, there's no separator in sight
+                _input = _input[_frontLength .. _frontLength];
+                _frontLength = _frontLength.max;
+                static if (isBidirectionalRange!Range)
+                    _backLength = _backLength.max;
+                return;
+            }
+            if (_frontLength + separatorLength == _input.length)
+            {
+                // Special case: popping the first-to-last item; there is
+                // an empty item right after this.
+                _input = _input[_input.length .. _input.length];
+                _frontLength = 0;
+                static if (isBidirectionalRange!Range)
+                    _backLength = 0;
+                return;
+            }
+            // Normal case, pop one item and the separator, get ready for
+            // reading the next item
+            _input = _input[_frontLength + separatorLength .. _input.length];
+            // mark _frontLength as uninitialized
+            _frontLength = _frontLength.max;
+        }
+
+        static if (isForwardRange!Range)
+        {
+            @property typeof(this) save()
+            {
+                auto ret = this;
+                ret._input = _input.save;
+                return ret;
+            }
+        }
+    }
+
+    return Result(r, s);
+}
+
+///
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+
+    assert(equal(splitter("hello  world", "  "), [ "hello", "world" ]));
+    int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ];
+    int[][] w = [ [1, 2], [3, 0, 4, 5, 0] ];
+    assert(equal(splitter(a, [0, 0]), w));
+    a = [ 0, 0 ];
+    assert(equal(splitter(a, [0, 0]), [ (int[]).init, (int[]).init ]));
+    a = [ 0, 0, 1 ];
+    assert(equal(splitter(a, [0, 0]), [ [], [1] ]));
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.typecons : Tuple;
+
+    alias C = Tuple!(int, "x", int, "y");
+    auto a = [C(1,0), C(2,0), C(3,1), C(4,0)];
+    assert(equal(splitter!"a.x == b"(a, [2, 3]), [ [C(1,0)], [C(4,0)] ]));
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.array : split;
+    import std.conv : text;
+
+    auto s = ",abc, de, fg,hi,";
+    auto sp0 = splitter(s, ',');
+    assert(equal(sp0, ["", "abc", " de", " fg", "hi", ""][]));
+
+    auto s1 = ", abc, de,  fg, hi, ";
+    auto sp1 = splitter(s1, ", ");
+    assert(equal(sp1, ["", "abc", "de", " fg", "hi", ""][]));
+    static assert(isForwardRange!(typeof(sp1)));
+
+    int[] a = [ 1, 2, 0, 3, 0, 4, 5, 0 ];
+    int[][] w = [ [1, 2], [3], [4, 5], [] ];
+    uint i;
+    foreach (e; splitter(a, 0))
+    {
+        assert(i < w.length);
+        assert(e == w[i++]);
+    }
+    assert(i == w.length);
+    // // Now go back
+    // auto s2 = splitter(a, 0);
+
+    // foreach (e; retro(s2))
+    // {
+    //     assert(i > 0);
+    //     assert(equal(e, w[--i]), text(e));
+    // }
+    // assert(i == 0);
+
+    wstring names = ",peter,paul,jerry,";
+    auto words = split(names, ",");
+    assert(walkLength(words) == 5, text(walkLength(words)));
+}
+
+@safe unittest
+{
+    int[][] a = [ [1], [2], [0], [3], [0], [4], [5], [0] ];
+    int[][][] w = [ [[1], [2]], [[3]], [[4], [5]], [] ];
+    uint i;
+    foreach (e; splitter!"a.front == 0"(a, 0))
+    {
+        assert(i < w.length);
+        assert(e == w[i++]);
+    }
+    assert(i == w.length);
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    auto s6 = ",";
+    auto sp6 = splitter(s6, ',');
+    foreach (e; sp6) {}
+    assert(equal(sp6, ["", ""][]));
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+
+    // Issue 10773
+    auto s = splitter("abc", "");
+    assert(s.equal(["a", "b", "c"]));
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+
+    // Test by-reference separator
+    class RefSep {
+    @safe:
+        string _impl;
+        this(string s) { _impl = s; }
+        @property empty() { return _impl.empty; }
+        @property auto front() { return _impl.front; }
+        void popFront() { _impl = _impl[1..$]; }
+        @property RefSep save() { return new RefSep(_impl); }
+        @property auto length() { return _impl.length; }
+    }
+    auto sep = new RefSep("->");
+    auto data = "i->am->pointing";
+    auto words = splitter(data, sep);
+    assert(words.equal([ "i", "am", "pointing" ]));
+}
+
+/**
+
+Similar to the previous overload of $(D splitter), except this one does not use a separator.
+Instead, the predicate is an unary function on the input range's element type.
+The $(D isTerminator) predicate is passed to $(REF unaryFun, std,functional) and can
+either accept a string, or any callable that can be executed via $(D pred(element, s)).
+
+Two adjacent separators are considered to surround an empty element in
+the split range. Use $(D filter!(a => !a.empty)) on the result to compress
+empty elements.
+
+Params:
+    isTerminator = The predicate for deciding where to split the range.
+    input = The $(REF_ALTTEXT input range, isInputRange, std,range,primitives) to
+        be split.
+
+Constraints:
+    The predicate $(D isTerminator) needs to accept an element of $(D input).
+
+Returns:
+    An input range of the subranges of elements between separators. If $(D input)
+    is a forward range or $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives),
+    the returned range will be likewise.
+
+See_Also: $(REF _splitter, std,regex) for a version that splits using a regular
+expression defined separator.
+ */
+auto splitter(alias isTerminator, Range)(Range input)
+if (isForwardRange!Range && is(typeof(unaryFun!isTerminator(input.front))))
+{
+    return SplitterResult!(unaryFun!isTerminator, Range)(input);
+}
+
+///
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range.primitives : front;
+
+    assert(equal(splitter!(a => a == ' ')("hello  world"), [ "hello", "", "world" ]));
+    int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ];
+    int[][] w = [ [1, 2], [], [3], [4, 5], [] ];
+    assert(equal(splitter!(a => a == 0)(a), w));
+    a = [ 0 ];
+    assert(equal(splitter!(a => a == 0)(a), [ (int[]).init, (int[]).init ]));
+    a = [ 0, 1 ];
+    assert(equal(splitter!(a => a == 0)(a), [ [], [1] ]));
+    w = [ [0], [1], [2] ];
+    assert(equal(splitter!(a => a.front == 1)(w), [ [[0]], [[2]] ]));
+}
+
+private struct SplitterResult(alias isTerminator, Range)
+{
+    import std.algorithm.searching : find;
+    enum fullSlicing = (hasLength!Range && hasSlicing!Range) || isSomeString!Range;
+
+    private Range _input;
+    private size_t _end = 0;
+    static if (!fullSlicing)
+        private Range _next;
+
+    private void findTerminator()
+    {
+        static if (fullSlicing)
+        {
+            auto r = find!isTerminator(_input.save);
+            _end = _input.length - r.length;
+        }
+        else
+            for ( _end = 0; !_next.empty ; _next.popFront)
+            {
+                if (isTerminator(_next.front))
+                    break;
+                ++_end;
+            }
+    }
+
+    this(Range input)
+    {
+        _input = input;
+        static if (!fullSlicing)
+            _next = _input.save;
+
+        if (!_input.empty)
+            findTerminator();
+        else
+            _end = size_t.max;
+    }
+
+    static if (isInfinite!Range)
+    {
+        enum bool empty = false;  // Propagate infiniteness.
+    }
+    else
+    {
+        @property bool empty()
+        {
+            return _end == size_t.max;
+        }
+    }
+
+    @property auto front()
+    {
+        version (assert)
+        {
+            import core.exception : RangeError;
+            if (empty)
+                throw new RangeError();
+        }
+        static if (fullSlicing)
+            return _input[0 .. _end];
+        else
+        {
+            import std.range : takeExactly;
+            return _input.takeExactly(_end);
+        }
+    }
+
+    void popFront()
+    {
+        version (assert)
+        {
+            import core.exception : RangeError;
+            if (empty)
+                throw new RangeError();
+        }
+
+        static if (fullSlicing)
+        {
+            _input = _input[_end .. _input.length];
+            if (_input.empty)
+            {
+                _end = size_t.max;
+                return;
+            }
+            _input.popFront();
+        }
+        else
+        {
+            if (_next.empty)
+            {
+                _input = _next;
+                _end = size_t.max;
+                return;
+            }
+            _next.popFront();
+            _input = _next.save;
+        }
+        findTerminator();
+    }
+
+    @property typeof(this) save()
+    {
+        auto ret = this;
+        ret._input = _input.save;
+        static if (!fullSlicing)
+            ret._next = _next.save;
+        return ret;
+    }
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range : iota;
+
+    auto L = iota(1L, 10L);
+    auto s = splitter(L, [5L, 6L]);
+    assert(equal(s.front, [1L, 2L, 3L, 4L]));
+    s.popFront();
+    assert(equal(s.front, [7L, 8L, 9L]));
+    s.popFront();
+    assert(s.empty);
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.algorithm.internal : algoFormat;
+    import std.internal.test.dummyrange;
+
+    void compare(string sentence, string[] witness)
+    {
+        auto r = splitter!"a == ' '"(sentence);
+        assert(equal(r.save, witness), algoFormat("got: %(%s, %) expected: %(%s, %)", r, witness));
+    }
+
+    compare(" Mary  has a little lamb.   ",
+            ["", "Mary", "", "has", "a", "little", "lamb.", "", "", ""]);
+    compare("Mary  has a little lamb.   ",
+            ["Mary", "", "has", "a", "little", "lamb.", "", "", ""]);
+    compare("Mary  has a little lamb.",
+            ["Mary", "", "has", "a", "little", "lamb."]);
+    compare("", (string[]).init);
+    compare(" ", ["", ""]);
+
+    static assert(isForwardRange!(typeof(splitter!"a == ' '"("ABC"))));
+
+    foreach (DummyType; AllDummyRanges)
+    {
+        static if (isRandomAccessRange!DummyType)
+        {
+            auto rangeSplit = splitter!"a == 5"(DummyType.init);
+            assert(equal(rangeSplit.front, [1,2,3,4]));
+            rangeSplit.popFront();
+            assert(equal(rangeSplit.front, [6,7,8,9,10]));
+        }
+    }
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.algorithm.internal : algoFormat;
+    import std.range;
+
+    struct Entry
+    {
+        int low;
+        int high;
+        int[][] result;
+    }
+    Entry[] entries = [
+        Entry(0, 0, []),
+        Entry(0, 1, [[0]]),
+        Entry(1, 2, [[], []]),
+        Entry(2, 7, [[2], [4], [6]]),
+        Entry(1, 8, [[], [2], [4], [6], []]),
+    ];
+    foreach ( entry ; entries )
+    {
+        auto a = iota(entry.low, entry.high).filter!"true"();
+        auto b = splitter!"a%2"(a);
+        assert(equal!equal(b.save, entry.result), algoFormat("got: %(%s, %) expected: %(%s, %)", b, entry.result));
+    }
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.uni : isWhite;
+
+    //@@@6791@@@
+    assert(equal(
+        splitter("là dove terminava quella valle"),
+        ["là", "dove", "terminava", "quella", "valle"]
+    ));
+    assert(equal(
+        splitter!(std.uni.isWhite)("là dove terminava quella valle"),
+        ["là", "dove", "terminava", "quella", "valle"]
+    ));
+    assert(equal(splitter!"a=='本'"("日本語"), ["日", "語"]));
+}
+
+/++
+Lazily splits the string $(D s) into words, using whitespace as the delimiter.
+
+This function is string specific and, contrary to
+$(D splitter!(std.uni.isWhite)), runs of whitespace will be merged together
+(no empty tokens will be produced).
+
+Params:
+    s = The string to be split.
+
+Returns:
+    An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) of slices of
+    the original string split by whitespace.
+ +/
+auto splitter(C)(C[] s)
+if (isSomeChar!C)
+{
+    import std.algorithm.searching : find;
+    static struct Result
+    {
+    private:
+        import core.exception : RangeError;
+        C[] _s;
+        size_t _frontLength;
+
+        void getFirst() pure @safe
+        {
+            import std.uni : isWhite;
+
+            auto r = find!(isWhite)(_s);
+            _frontLength = _s.length - r.length;
+        }
+
+    public:
+        this(C[] s) pure @safe
+        {
+            import std.string : strip;
+            _s = s.strip();
+            getFirst();
+        }
+
+        @property C[] front() pure @safe
+        {
+            version (assert) if (empty) throw new RangeError();
+            return _s[0 .. _frontLength];
+        }
+
+        void popFront() pure @safe
+        {
+            import std.string : stripLeft;
+            version (assert) if (empty) throw new RangeError();
+            _s = _s[_frontLength .. $].stripLeft();
+            getFirst();
+        }
+
+        @property bool empty() const @safe pure nothrow
+        {
+            return _s.empty;
+        }
+
+        @property inout(Result) save() inout @safe pure nothrow
+        {
+            return this;
+        }
+    }
+    return Result(s);
+}
+
+///
+@safe pure unittest
+{
+    import std.algorithm.comparison : equal;
+    auto a = " a     bcd   ef gh ";
+    assert(equal(splitter(a), ["a", "bcd", "ef", "gh"][]));
+}
+
+@safe pure unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.meta : AliasSeq;
+    foreach (S; AliasSeq!(string, wstring, dstring))
+    {
+        import std.conv : to;
+        S a = " a     bcd   ef gh ";
+        assert(equal(splitter(a), [to!S("a"), to!S("bcd"), to!S("ef"), to!S("gh")]));
+        a = "";
+        assert(splitter(a).empty);
+    }
+
+    immutable string s = " a     bcd   ef gh ";
+    assert(equal(splitter(s), ["a", "bcd", "ef", "gh"][]));
+}
+
+@safe unittest
+{
+    import std.conv : to;
+    import std.string : strip;
+
+    // TDPL example, page 8
+    uint[string] dictionary;
+    char[][3] lines;
+    lines[0] = "line one".dup;
+    lines[1] = "line \ttwo".dup;
+    lines[2] = "yah            last   line\ryah".dup;
+    foreach (line; lines)
+    {
+       foreach (word; splitter(strip(line)))
+       {
+            if (word in dictionary) continue; // Nothing to do
+            auto newID = dictionary.length;
+            dictionary[to!string(word)] = cast(uint) newID;
+        }
+    }
+    assert(dictionary.length == 5);
+    assert(dictionary["line"]== 0);
+    assert(dictionary["one"]== 1);
+    assert(dictionary["two"]== 2);
+    assert(dictionary["yah"]== 3);
+    assert(dictionary["last"]== 4);
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.algorithm.internal : algoFormat;
+    import std.array : split;
+    import std.conv : text;
+
+    // Check consistency:
+    // All flavors of split should produce the same results
+    foreach (input; [(int[]).init,
+                     [0],
+                     [0, 1, 0],
+                     [1, 1, 0, 0, 1, 1],
+                    ])
+    {
+        foreach (s; [0, 1])
+        {
+            auto result = split(input, s);
+
+            assert(equal(result, split(input, [s])), algoFormat(`"[%(%s,%)]"`, split(input, [s])));
+            //assert(equal(result, split(input, [s].filter!"true"())));                          //Not yet implemented
+            assert(equal(result, split!((a) => a == s)(input)), text(split!((a) => a == s)(input)));
+
+            //assert(equal!equal(result, split(input.filter!"true"(), s)));                      //Not yet implemented
+            //assert(equal!equal(result, split(input.filter!"true"(), [s])));                    //Not yet implemented
+            //assert(equal!equal(result, split(input.filter!"true"(), [s].filter!"true"())));    //Not yet implemented
+            assert(equal!equal(result, split!((a) => a == s)(input.filter!"true"())));
+
+            assert(equal(result, splitter(input, s)));
+            assert(equal(result, splitter(input, [s])));
+            //assert(equal(result, splitter(input, [s].filter!"true"())));                       //Not yet implemented
+            assert(equal(result, splitter!((a) => a == s)(input)));
+
+            //assert(equal!equal(result, splitter(input.filter!"true"(), s)));                   //Not yet implemented
+            //assert(equal!equal(result, splitter(input.filter!"true"(), [s])));                 //Not yet implemented
+            //assert(equal!equal(result, splitter(input.filter!"true"(), [s].filter!"true"()))); //Not yet implemented
+            assert(equal!equal(result, splitter!((a) => a == s)(input.filter!"true"())));
+        }
+    }
+    foreach (input; [string.init,
+                     " ",
+                     "  hello ",
+                     "hello   hello",
+                     " hello   what heck   this ?  "
+                    ])
+    {
+        foreach (s; [' ', 'h'])
+        {
+            auto result = split(input, s);
+
+            assert(equal(result, split(input, [s])));
+            //assert(equal(result, split(input, [s].filter!"true"())));                          //Not yet implemented
+            assert(equal(result, split!((a) => a == s)(input)));
+
+            //assert(equal!equal(result, split(input.filter!"true"(), s)));                      //Not yet implemented
+            //assert(equal!equal(result, split(input.filter!"true"(), [s])));                    //Not yet implemented
+            //assert(equal!equal(result, split(input.filter!"true"(), [s].filter!"true"())));    //Not yet implemented
+            assert(equal!equal(result, split!((a) => a == s)(input.filter!"true"())));
+
+            assert(equal(result, splitter(input, s)));
+            assert(equal(result, splitter(input, [s])));
+            //assert(equal(result, splitter(input, [s].filter!"true"())));                       //Not yet implemented
+            assert(equal(result, splitter!((a) => a == s)(input)));
+
+            //assert(equal!equal(result, splitter(input.filter!"true"(), s)));                   //Not yet implemented
+            //assert(equal!equal(result, splitter(input.filter!"true"(), [s])));                 //Not yet implemented
+            //assert(equal!equal(result, splitter(input.filter!"true"(), [s].filter!"true"()))); //Not yet implemented
+            assert(equal!equal(result, splitter!((a) => a == s)(input.filter!"true"())));
+        }
+    }
+}
+
+// sum
+/**
+Sums elements of $(D r), which must be a finite
+$(REF_ALTTEXT input range, isInputRange, std,range,primitives). Although
+conceptually $(D sum(r)) is equivalent to $(LREF fold)!((a, b) => a +
+b)(r, 0), $(D sum) uses specialized algorithms to maximize accuracy,
+as follows.
+
+$(UL
+$(LI If $(D $(REF ElementType, std,range,primitives)!R) is a floating-point
+type and $(D R) is a
+$(REF_ALTTEXT random-access range, isRandomAccessRange, std,range,primitives) with
+length and slicing, then $(D sum) uses the
+$(HTTP en.wikipedia.org/wiki/Pairwise_summation, pairwise summation)
+algorithm.)
+$(LI If $(D ElementType!R) is a floating-point type and $(D R) is a
+finite input range (but not a random-access range with slicing), then
+$(D sum) uses the $(HTTP en.wikipedia.org/wiki/Kahan_summation,
+Kahan summation) algorithm.)
+$(LI In all other cases, a simple element by element addition is done.)
+)
+
+For floating point inputs, calculations are made in
+$(DDLINK spec/type, Types, $(D real))
+precision for $(D real) inputs and in $(D double) precision otherwise
+(Note this is a special case that deviates from $(D fold)'s behavior,
+which would have kept $(D float) precision for a $(D float) range).
+For all other types, the calculations are done in the same type obtained
+from from adding two elements of the range, which may be a different
+type from the elements themselves (for example, in case of
+$(DDSUBLINK spec/type,integer-promotions, integral promotion)).
+
+A seed may be passed to $(D sum). Not only will this seed be used as an initial
+value, but its type will override all the above, and determine the algorithm
+and precision used for summation.
+
+Note that these specialized summing algorithms execute more primitive operations
+than vanilla summation. Therefore, if in certain cases maximum speed is required
+at expense of precision, one can use $(D fold!((a, b) => a + b)(r, 0)), which
+is not specialized for summation.
+
+Params:
+    seed = the initial value of the summation
+    r = a finite input range
+
+Returns:
+    The sum of all the elements in the range r.
+ */
+auto sum(R)(R r)
+if (isInputRange!R && !isInfinite!R && is(typeof(r.front + r.front)))
+{
+    alias E = Unqual!(ElementType!R);
+    static if (isFloatingPoint!E)
+        alias Seed = typeof(E.init  + 0.0); //biggest of double/real
+    else
+        alias Seed = typeof(r.front + r.front);
+    return sum(r, Unqual!Seed(0));
+}
+/// ditto
+auto sum(R, E)(R r, E seed)
+if (isInputRange!R && !isInfinite!R && is(typeof(seed = seed + r.front)))
+{
+    static if (isFloatingPoint!E)
+    {
+        static if (hasLength!R && hasSlicing!R)
+        {
+            if (r.empty) return seed;
+            return seed + sumPairwise!E(r);
+        }
+        else
+            return sumKahan!E(seed, r);
+    }
+    else
+    {
+        return reduce!"a + b"(seed, r);
+    }
+}
+
+// Pairwise summation http://en.wikipedia.org/wiki/Pairwise_summation
+private auto sumPairwise(F, R)(R data)
+if (isInputRange!R && !isInfinite!R)
+{
+    import core.bitop : bsf;
+    // Works for r with at least length < 2^^(64 + log2(16)), in keeping with the use of size_t
+    // elsewhere in std.algorithm and std.range on 64 bit platforms. The 16 in log2(16) comes
+    // from the manual unrolling in sumPairWise16
+    F[64] store = void;
+    size_t idx = 0;
+
+    void collapseStore(T)(T k)
+    {
+        auto lastToKeep = idx - cast(uint) bsf(k+1);
+        while (idx > lastToKeep)
+        {
+            store[idx - 1] += store[idx];
+            --idx;
+        }
+    }
+
+    static if (hasLength!R)
+    {
+        foreach (k; 0 .. data.length / 16)
+        {
+            static if (isRandomAccessRange!R && hasSlicing!R)
+            {
+                store[idx] = sumPairwise16!F(data);
+                data = data[16 .. data.length];
+            }
+            else store[idx] = sumPairwiseN!(16, false, F)(data);
+
+            collapseStore(k);
+            ++idx;
+        }
+
+        size_t i = 0;
+        foreach (el; data)
+        {
+            store[idx] = el;
+            collapseStore(i);
+            ++idx;
+            ++i;
+        }
+    }
+    else
+    {
+        size_t k = 0;
+        while (!data.empty)
+        {
+            store[idx] = sumPairwiseN!(16, true, F)(data);
+            collapseStore(k);
+            ++idx;
+            ++k;
+        }
+    }
+
+    F s = store[idx - 1];
+    foreach_reverse (j; 0 .. idx - 1)
+        s += store[j];
+
+    return s;
+}
+
+private auto sumPairwise16(F, R)(R r)
+if (isRandomAccessRange!R)
+{
+    return (((cast(F) r[ 0] + r[ 1]) + (cast(F) r[ 2] + r[ 3]))
+          + ((cast(F) r[ 4] + r[ 5]) + (cast(F) r[ 6] + r[ 7])))
+         + (((cast(F) r[ 8] + r[ 9]) + (cast(F) r[10] + r[11]))
+          + ((cast(F) r[12] + r[13]) + (cast(F) r[14] + r[15])));
+}
+
+private auto sumPair(bool needEmptyChecks, F, R)(ref R r)
+if (isForwardRange!R && !isRandomAccessRange!R)
+{
+    static if (needEmptyChecks) if (r.empty) return F(0);
+    F s0 = r.front;
+    r.popFront();
+    static if (needEmptyChecks) if (r.empty) return s0;
+    s0 += r.front;
+    r.popFront();
+    return s0;
+}
+
+private auto sumPairwiseN(size_t N, bool needEmptyChecks, F, R)(ref R r)
+if (isForwardRange!R && !isRandomAccessRange!R)
+{
+    import std.math : isPowerOf2;
+    static assert(isPowerOf2(N));
+    static if (N == 2) return sumPair!(needEmptyChecks, F)(r);
+    else return sumPairwiseN!(N/2, needEmptyChecks, F)(r)
+        + sumPairwiseN!(N/2, needEmptyChecks, F)(r);
+}
+
+// Kahan algo http://en.wikipedia.org/wiki/Kahan_summation_algorithm
+private auto sumKahan(Result, R)(Result result, R r)
+{
+    static assert(isFloatingPoint!Result && isMutable!Result);
+    Result c = 0;
+    for (; !r.empty; r.popFront())
+    {
+        immutable y = r.front - c;
+        immutable t = result + y;
+        c = (t - result) - y;
+        result = t;
+    }
+    return result;
+}
+
+/// Ditto
+@safe pure nothrow unittest
+{
+    import std.range;
+
+    //simple integral sumation
+    assert(sum([ 1, 2, 3, 4]) == 10);
+
+    //with integral promotion
+    assert(sum([false, true, true, false, true]) == 3);
+    assert(sum(ubyte.max.repeat(100)) == 25500);
+
+    //The result may overflow
+    assert(uint.max.repeat(3).sum()           ==  4294967293U );
+    //But a seed can be used to change the sumation primitive
+    assert(uint.max.repeat(3).sum(ulong.init) == 12884901885UL);
+
+    //Floating point sumation
+    assert(sum([1.0, 2.0, 3.0, 4.0]) == 10);
+
+    //Floating point operations have double precision minimum
+    static assert(is(typeof(sum([1F, 2F, 3F, 4F])) == double));
+    assert(sum([1F, 2, 3, 4]) == 10);
+
+    //Force pair-wise floating point sumation on large integers
+    import std.math : approxEqual;
+    assert(iota(ulong.max / 2, ulong.max / 2 + 4096).sum(0.0)
+               .approxEqual((ulong.max / 2) * 4096.0 + 4096^^2 / 2));
+}
+
+@safe pure nothrow unittest
+{
+    static assert(is(typeof(sum([cast( byte) 1])) ==  int));
+    static assert(is(typeof(sum([cast(ubyte) 1])) ==  int));
+    static assert(is(typeof(sum([  1,   2,   3,   4])) ==  int));
+    static assert(is(typeof(sum([ 1U,  2U,  3U,  4U])) == uint));
+    static assert(is(typeof(sum([ 1L,  2L,  3L,  4L])) ==  long));
+    static assert(is(typeof(sum([1UL, 2UL, 3UL, 4UL])) == ulong));
+
+    int[] empty;
+    assert(sum(empty) == 0);
+    assert(sum([42]) == 42);
+    assert(sum([42, 43]) == 42 + 43);
+    assert(sum([42, 43, 44]) == 42 + 43 + 44);
+    assert(sum([42, 43, 44, 45]) == 42 + 43 + 44 + 45);
+}
+
+@safe pure nothrow unittest
+{
+    static assert(is(typeof(sum([1.0, 2.0, 3.0, 4.0])) == double));
+    static assert(is(typeof(sum([ 1F,  2F,  3F,  4F])) == double));
+    const(float[]) a = [1F, 2F, 3F, 4F];
+    assert(sum(a) == 10F);
+    static assert(is(typeof(sum(a)) == double));
+
+    double[] empty;
+    assert(sum(empty) == 0);
+    assert(sum([42.]) == 42);
+    assert(sum([42., 43.]) == 42 + 43);
+    assert(sum([42., 43., 44.]) == 42 + 43 + 44);
+    assert(sum([42., 43., 44., 45.5]) == 42 + 43 + 44 + 45.5);
+}
+
+@safe pure nothrow unittest
+{
+    import std.container;
+    static assert(is(typeof(sum(SList!float()[])) == double));
+    static assert(is(typeof(sum(SList!double()[])) == double));
+    static assert(is(typeof(sum(SList!real()[])) == real));
+
+    assert(sum(SList!double()[]) == 0);
+    assert(sum(SList!double(1)[]) == 1);
+    assert(sum(SList!double(1, 2)[]) == 1 + 2);
+    assert(sum(SList!double(1, 2, 3)[]) == 1 + 2 + 3);
+    assert(sum(SList!double(1, 2, 3, 4)[]) == 10);
+}
+
+@safe pure nothrow unittest // 12434
+{
+    immutable a = [10, 20];
+    auto s1 = sum(a);
+    assert(s1 == 30);
+    auto s2 = a.map!(x => x).sum;
+    assert(s2 == 30);
+}
+
+@system unittest
+{
+    import std.bigint;
+    import std.range;
+
+    immutable BigInt[] a = BigInt("1_000_000_000_000_000_000").repeat(10).array();
+    immutable ulong[]  b = (ulong.max/2).repeat(10).array();
+    auto sa = a.sum();
+    auto sb = b.sum(BigInt(0)); //reduce ulongs into bigint
+    assert(sa == BigInt("10_000_000_000_000_000_000"));
+    assert(sb == (BigInt(ulong.max/2) * 10));
+}
+
+@safe pure nothrow @nogc unittest
+{
+    import std.range;
+    foreach (n; iota(50))
+        assert(repeat(1.0, n).sum == n);
+}
+
+// uniq
+/**
+Lazily iterates unique consecutive elements of the given range (functionality
+akin to the $(HTTP wikipedia.org/wiki/_Uniq, _uniq) system
+utility). Equivalence of elements is assessed by using the predicate
+$(D pred), by default $(D "a == b"). The predicate is passed to
+$(REF binaryFun, std,functional), and can either accept a string, or any callable
+that can be executed via $(D pred(element, element)). If the given range is
+bidirectional, $(D uniq) also yields a
+$(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives).
+
+Params:
+    pred = Predicate for determining equivalence between range elements.
+    r = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) of
+        elements to filter.
+
+Returns:
+    An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) of
+    consecutively unique elements in the original range. If $(D r) is also a
+    forward range or bidirectional range, the returned range will be likewise.
+*/
+auto uniq(alias pred = "a == b", Range)(Range r)
+if (isInputRange!Range && is(typeof(binaryFun!pred(r.front, r.front)) == bool))
+{
+    return UniqResult!(binaryFun!pred, Range)(r);
+}
+
+///
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.algorithm.mutation : copy;
+
+    int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
+    assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][]));
+
+    // Filter duplicates in-place using copy
+    arr.length -= arr.uniq().copy(arr).length;
+    assert(arr == [ 1, 2, 3, 4, 5 ]);
+
+    // Note that uniqueness is only determined consecutively; duplicated
+    // elements separated by an intervening different element will not be
+    // eliminated:
+    assert(equal(uniq([ 1, 1, 2, 1, 1, 3, 1]), [1, 2, 1, 3, 1]));
+}
+
+private struct UniqResult(alias pred, Range)
+{
+    Range _input;
+
+    this(Range input)
+    {
+        _input = input;
+    }
+
+    auto opSlice()
+    {
+        return this;
+    }
+
+    void popFront()
+    {
+        assert(!empty, "Attempting to popFront an empty uniq.");
+        auto last = _input.front;
+        do
+        {
+            _input.popFront();
+        }
+        while (!_input.empty && pred(last, _input.front));
+    }
+
+    @property ElementType!Range front()
+    {
+        assert(!empty, "Attempting to fetch the front of an empty uniq.");
+        return _input.front;
+    }
+
+    static if (isBidirectionalRange!Range)
+    {
+        void popBack()
+        {
+            assert(!empty, "Attempting to popBack an empty uniq.");
+            auto last = _input.back;
+            do
+            {
+                _input.popBack();
+            }
+            while (!_input.empty && pred(last, _input.back));
+        }
+
+        @property ElementType!Range back()
+        {
+            assert(!empty, "Attempting to fetch the back of an empty uniq.");
+            return _input.back;
+        }
+    }
+
+    static if (isInfinite!Range)
+    {
+        enum bool empty = false;  // Propagate infiniteness.
+    }
+    else
+    {
+        @property bool empty() { return _input.empty; }
+    }
+
+    static if (isForwardRange!Range)
+    {
+        @property typeof(this) save() {
+            return typeof(this)(_input.save);
+        }
+    }
+}
+
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.internal.test.dummyrange;
+    import std.range;
+
+    int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
+    auto r = uniq(arr);
+    static assert(isForwardRange!(typeof(r)));
+
+    assert(equal(r, [ 1, 2, 3, 4, 5 ][]));
+    assert(equal(retro(r), retro([ 1, 2, 3, 4, 5 ][])));
+
+    foreach (DummyType; AllDummyRanges)
+    {
+        DummyType d;
+        auto u = uniq(d);
+        assert(equal(u, [1,2,3,4,5,6,7,8,9,10]));
+
+        static assert(d.rt == RangeType.Input || isForwardRange!(typeof(u)));
+
+        static if (d.rt >= RangeType.Bidirectional)
+        {
+            assert(equal(retro(u), [10,9,8,7,6,5,4,3,2,1]));
+        }
+    }
+}
+
+@safe unittest // https://issues.dlang.org/show_bug.cgi?id=17264
+{
+    import std.algorithm.comparison : equal;
+
+    const(int)[] var = [0, 1, 1, 2];
+    assert(var.uniq.equal([0, 1, 2]));
+}
+
+/**
+Lazily computes all _permutations of $(D r) using $(HTTP
+en.wikipedia.org/wiki/Heap%27s_algorithm, Heap's algorithm).
+
+Returns:
+A $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
+the elements of which are an $(REF indexed, std,range) view into $(D r).
+
+See_Also:
+$(REF nextPermutation, std,algorithm,sorting).
+*/
+Permutations!Range permutations(Range)(Range r)
+if (isRandomAccessRange!Range && hasLength!Range)
+{
+    return typeof(return)(r);
+}
+
+/// ditto
+struct Permutations(Range)
+if (isRandomAccessRange!Range && hasLength!Range)
+{
+    private size_t[] _indices, _state;
+    private Range _r;
+    private bool _empty;
+
+    ///
+    this(Range r)
+    {
+        import std.array : array;
+        import std.range : iota;
+
+        this._r = r;
+        _state = r.length ? new size_t[r.length-1] : null;
+        _indices = iota(size_t(r.length)).array;
+        _empty = r.length == 0;
+    }
+
+    ///
+    @property bool empty() const pure nothrow @safe @nogc
+    {
+        return _empty;
+    }
+
+    ///
+    @property auto front()
+    {
+        import std.range : indexed;
+        return _r.indexed(_indices);
+    }
+
+    ///
+    void popFront()
+    {
+        void next(int n)
+        {
+            import std.algorithm.mutation : swap;
+
+            if (n > _indices.length)
+            {
+                _empty = true;
+                return;
+            }
+
+            if (n % 2 == 1)
+                swap(_indices[0], _indices[n-1]);
+            else
+                swap(_indices[_state[n-2]], _indices[n-1]);
+
+            if (++_state[n-2] == n)
+            {
+                _state[n-2] = 0;
+                next(n+1);
+            }
+        }
+
+        next(2);
+    }
+}
+
+///
+@safe unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range : iota;
+    assert(equal!equal(iota(3).permutations,
+        [[0, 1, 2],
+         [1, 0, 2],
+         [2, 0, 1],
+         [0, 2, 1],
+         [1, 2, 0],
+         [2, 1, 0]]));
+}