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, 595 insertions, 0 deletions

diff --git a/libphobos/src/std/container/binaryheap.d b/libphobos/src/std/container/binaryheap.d
new file mode 100644
index 0000000..4adf604
--- /dev/null
+++ b/libphobos/src/std/container/binaryheap.d
@@ -0,0 +1,595 @@
+/**
+This module provides a $(D BinaryHeap) (aka priority queue)
+adaptor that makes a binary heap out of any user-provided random-access range.
+
+This module is a submodule of $(MREF std, container).
+
+Source: $(PHOBOSSRC std/container/_binaryheap.d)
+
+Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders.
+
+License: Distributed under the Boost Software License, Version 1.0.
+(See accompanying file LICENSE_1_0.txt or copy at $(HTTP
+boost.org/LICENSE_1_0.txt)).
+
+Authors: $(HTTP erdani.com, Andrei Alexandrescu)
+*/
+module std.container.binaryheap;
+
+import std.range.primitives;
+import std.traits;
+
+public import std.container.util;
+
+///
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range : take;
+    auto maxHeap = heapify([4, 7, 3, 1, 5]);
+    assert(maxHeap.take(3).equal([7, 5, 4]));
+
+    auto minHeap = heapify!"a > b"([4, 7, 3, 1, 5]);
+    assert(minHeap.take(3).equal([1, 3, 4]));
+}
+
+// BinaryHeap
+/**
+Implements a $(HTTP en.wikipedia.org/wiki/Binary_heap, binary heap)
+container on top of a given random-access range type (usually $(D
+T[])) or a random-access container type (usually $(D Array!T)). The
+documentation of $(D BinaryHeap) will refer to the underlying range or
+container as the $(I store) of the heap.
+
+The binary heap induces structure over the underlying store such that
+accessing the largest element (by using the $(D front) property) is a
+$(BIGOH 1) operation and extracting it (by using the $(D
+removeFront()) method) is done fast in $(BIGOH log n) time.
+
+If $(D less) is the less-than operator, which is the default option,
+then $(D BinaryHeap) defines a so-called max-heap that optimizes
+extraction of the $(I largest) elements. To define a min-heap,
+instantiate BinaryHeap with $(D "a > b") as its predicate.
+
+Simply extracting elements from a $(D BinaryHeap) container is
+tantamount to lazily fetching elements of $(D Store) in descending
+order. Extracting elements from the $(D BinaryHeap) to completion
+leaves the underlying store sorted in ascending order but, again,
+yields elements in descending order.
+
+If $(D Store) is a range, the $(D BinaryHeap) cannot grow beyond the
+size of that range. If $(D Store) is a container that supports $(D
+insertBack), the $(D BinaryHeap) may grow by adding elements to the
+container.
+     */
+struct BinaryHeap(Store, alias less = "a < b")
+if (isRandomAccessRange!(Store) || isRandomAccessRange!(typeof(Store.init[])))
+{
+    import std.algorithm.comparison : min;
+    import std.algorithm.mutation : move, swapAt;
+    import std.algorithm.sorting : HeapOps;
+    import std.exception : enforce;
+    import std.functional : binaryFun;
+    import std.typecons : RefCounted, RefCountedAutoInitialize;
+
+    static if (isRandomAccessRange!Store)
+        alias Range = Store;
+    else
+        alias Range = typeof(Store.init[]);
+    alias percolate = HeapOps!(less, Range).percolate;
+    alias buildHeap = HeapOps!(less, Range).buildHeap;
+
+// Really weird @@BUG@@: if you comment out the "private:" label below,
+// std.algorithm can't unittest anymore
+//private:
+
+    // The payload includes the support store and the effective length
+    private static struct Data
+    {
+        Store _store;
+        size_t _length;
+    }
+    private RefCounted!(Data, RefCountedAutoInitialize.no) _payload;
+    // Comparison predicate
+    private alias comp = binaryFun!(less);
+    // Convenience accessors
+    private @property ref Store _store()
+    {
+        assert(_payload.refCountedStore.isInitialized);
+        return _payload._store;
+    }
+    private @property ref size_t _length()
+    {
+        assert(_payload.refCountedStore.isInitialized);
+        return _payload._length;
+    }
+
+    // Asserts that the heap property is respected.
+    private void assertValid()
+    {
+        debug
+        {
+            import std.conv : to;
+            if (!_payload.refCountedStore.isInitialized) return;
+            if (_length < 2) return;
+            for (size_t n = _length - 1; n >= 1; --n)
+            {
+                auto parentIdx = (n - 1) / 2;
+                assert(!comp(_store[parentIdx], _store[n]), to!string(n));
+            }
+        }
+    }
+
+    // @@@BUG@@@: add private here, std.algorithm doesn't unittest anymore
+    /*private*/ void pop(Store store)
+    {
+        assert(!store.empty, "Cannot pop an empty store.");
+        if (store.length == 1) return;
+        auto t1 = store[].moveFront();
+        auto t2 = store[].moveBack();
+        store.front = move(t2);
+        store.back = move(t1);
+        percolate(store[], 0, store.length - 1);
+    }
+
+public:
+
+    /**
+       Converts the store $(D s) into a heap. If $(D initialSize) is
+       specified, only the first $(D initialSize) elements in $(D s)
+       are transformed into a heap, after which the heap can grow up
+       to $(D r.length) (if $(D Store) is a range) or indefinitely (if
+       $(D Store) is a container with $(D insertBack)). Performs
+       $(BIGOH min(r.length, initialSize)) evaluations of $(D less).
+     */
+    this(Store s, size_t initialSize = size_t.max)
+    {
+        acquire(s, initialSize);
+    }
+
+/**
+Takes ownership of a store. After this, manipulating $(D s) may make
+the heap work incorrectly.
+     */
+    void acquire(Store s, size_t initialSize = size_t.max)
+    {
+        _payload.refCountedStore.ensureInitialized();
+        _store = move(s);
+        _length = min(_store.length, initialSize);
+        if (_length < 2) return;
+        buildHeap(_store[]);
+        assertValid();
+    }
+
+/**
+Takes ownership of a store assuming it already was organized as a
+heap.
+     */
+    void assume(Store s, size_t initialSize = size_t.max)
+    {
+        _payload.refCountedStore.ensureInitialized();
+        _store = s;
+        _length = min(_store.length, initialSize);
+        assertValid();
+    }
+
+/**
+Clears the heap. Returns the portion of the store from $(D 0) up to
+$(D length), which satisfies the $(LINK2 https://en.wikipedia.org/wiki/Heap_(data_structure),
+heap property).
+     */
+    auto release()
+    {
+        if (!_payload.refCountedStore.isInitialized)
+        {
+            return typeof(_store[0 .. _length]).init;
+        }
+        assertValid();
+        auto result = _store[0 .. _length];
+        _payload = _payload.init;
+        return result;
+    }
+
+/**
+Returns $(D true) if the heap is _empty, $(D false) otherwise.
+     */
+    @property bool empty()
+    {
+        return !length;
+    }
+
+/**
+Returns a duplicate of the heap. The $(D dup) method is available only if the
+underlying store supports it.
+     */
+    static if (is(typeof((Store s) { return s.dup; }(Store.init)) == Store))
+    {
+        @property BinaryHeap dup()
+        {
+            BinaryHeap result;
+            if (!_payload.refCountedStore.isInitialized) return result;
+            result.assume(_store.dup, length);
+            return result;
+        }
+    }
+
+/**
+Returns the _length of the heap.
+     */
+    @property size_t length()
+    {
+        return _payload.refCountedStore.isInitialized ? _length : 0;
+    }
+
+/**
+Returns the _capacity of the heap, which is the length of the
+underlying store (if the store is a range) or the _capacity of the
+underlying store (if the store is a container).
+     */
+    @property size_t capacity()
+    {
+        if (!_payload.refCountedStore.isInitialized) return 0;
+        static if (is(typeof(_store.capacity) : size_t))
+        {
+            return _store.capacity;
+        }
+        else
+        {
+            return _store.length;
+        }
+    }
+
+/**
+Returns a copy of the _front of the heap, which is the largest element
+according to $(D less).
+     */
+    @property ElementType!Store front()
+    {
+        enforce(!empty, "Cannot call front on an empty heap.");
+        return _store.front;
+    }
+
+/**
+Clears the heap by detaching it from the underlying store.
+     */
+    void clear()
+    {
+        _payload = _payload.init;
+    }
+
+/**
+Inserts $(D value) into the store. If the underlying store is a range
+and $(D length == capacity), throws an exception.
+     */
+    size_t insert(ElementType!Store value)
+    {
+        static if (is(typeof(_store.insertBack(value))))
+        {
+            _payload.refCountedStore.ensureInitialized();
+            if (length == _store.length)
+            {
+                // reallocate
+                _store.insertBack(value);
+            }
+            else
+            {
+                // no reallocation
+                _store[_length] = value;
+            }
+        }
+        else
+        {
+            import std.traits : isDynamicArray;
+            static if (isDynamicArray!Store)
+            {
+                if (length == _store.length)
+                    _store.length = (length < 6 ? 8 : length * 3 / 2);
+                _store[_length] = value;
+            }
+            else
+            {
+                // can't grow
+                enforce(length < _store.length,
+                        "Cannot grow a heap created over a range");
+            }
+        }
+
+        // sink down the element
+        for (size_t n = _length; n; )
+        {
+            auto parentIdx = (n - 1) / 2;
+            if (!comp(_store[parentIdx], _store[n])) break; // done!
+            // must swap and continue
+            _store.swapAt(parentIdx, n);
+            n = parentIdx;
+        }
+        ++_length;
+        debug(BinaryHeap) assertValid();
+        return 1;
+    }
+
+/**
+Removes the largest element from the heap.
+     */
+    void removeFront()
+    {
+        enforce(!empty, "Cannot call removeFront on an empty heap.");
+        if (_length > 1)
+        {
+            auto t1 = _store[].moveFront();
+            auto t2 = _store[].moveAt(_length - 1);
+            _store.front = move(t2);
+            _store[_length - 1] = move(t1);
+        }
+        --_length;
+        percolate(_store[], 0, _length);
+    }
+
+    /// ditto
+    alias popFront = removeFront;
+
+/**
+Removes the largest element from the heap and returns a copy of
+it. The element still resides in the heap's store. For performance
+reasons you may want to use $(D removeFront) with heaps of objects
+that are expensive to copy.
+     */
+    ElementType!Store removeAny()
+    {
+        removeFront();
+        return _store[_length];
+    }
+
+/**
+Replaces the largest element in the store with $(D value).
+     */
+    void replaceFront(ElementType!Store value)
+    {
+        // must replace the top
+        assert(!empty, "Cannot call replaceFront on an empty heap.");
+        _store.front = value;
+        percolate(_store[], 0, _length);
+        debug(BinaryHeap) assertValid();
+    }
+
+/**
+If the heap has room to grow, inserts $(D value) into the store and
+returns $(D true). Otherwise, if $(D less(value, front)), calls $(D
+replaceFront(value)) and returns again $(D true). Otherwise, leaves
+the heap unaffected and returns $(D false). This method is useful in
+scenarios where the smallest $(D k) elements of a set of candidates
+must be collected.
+     */
+    bool conditionalInsert(ElementType!Store value)
+    {
+        _payload.refCountedStore.ensureInitialized();
+        if (_length < _store.length)
+        {
+            insert(value);
+            return true;
+        }
+
+        assert(!_store.empty, "Cannot replace front of an empty heap.");
+        if (!comp(value, _store.front)) return false; // value >= largest
+        _store.front = value;
+
+        percolate(_store[], 0, _length);
+        debug(BinaryHeap) assertValid();
+        return true;
+    }
+
+/**
+Swapping is allowed if the heap is full. If $(D less(value, front)), the
+method exchanges store.front and value and returns $(D true). Otherwise, it
+leaves the heap unaffected and returns $(D false).
+     */
+    bool conditionalSwap(ref ElementType!Store value)
+    {
+        _payload.refCountedStore.ensureInitialized();
+        assert(_length == _store.length);
+        assert(!_store.empty, "Cannot swap front of an empty heap.");
+
+        if (!comp(value, _store.front)) return false; // value >= largest
+
+        import std.algorithm.mutation : swap;
+        swap(_store.front, value);
+
+        percolate(_store[], 0, _length);
+        debug(BinaryHeap) assertValid();
+
+        return true;
+    }
+}
+
+/// Example from "Introduction to Algorithms" Cormen et al, p 146
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
+    auto h = heapify(a);
+    // largest element
+    assert(h.front == 16);
+    // a has the heap property
+    assert(equal(a, [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]));
+}
+
+/// $(D BinaryHeap) implements the standard input range interface, allowing
+/// lazy iteration of the underlying range in descending order.
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.range : take;
+    int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
+    auto top5 = heapify(a).take(5);
+    assert(top5.equal([16, 14, 10, 9, 8]));
+}
+
+/**
+Convenience function that returns a $(D BinaryHeap!Store) object
+initialized with $(D s) and $(D initialSize).
+ */
+BinaryHeap!(Store, less) heapify(alias less = "a < b", Store)(Store s,
+        size_t initialSize = size_t.max)
+{
+
+    return BinaryHeap!(Store, less)(s, initialSize);
+}
+
+///
+@system unittest
+{
+    import std.conv : to;
+    import std.range.primitives;
+    {
+        // example from "Introduction to Algorithms" Cormen et al., p 146
+        int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
+        auto h = heapify(a);
+        h = heapify!"a < b"(a);
+        assert(h.front == 16);
+        assert(a == [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]);
+        auto witness = [ 16, 14, 10, 9, 8, 7, 4, 3, 2, 1 ];
+        for (; !h.empty; h.removeFront(), witness.popFront())
+        {
+            assert(!witness.empty);
+            assert(witness.front == h.front);
+        }
+        assert(witness.empty);
+    }
+    {
+        int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
+        int[] b = new int[a.length];
+        BinaryHeap!(int[]) h = BinaryHeap!(int[])(b, 0);
+        foreach (e; a)
+        {
+            h.insert(e);
+        }
+        assert(b == [ 16, 14, 10, 8, 7, 3, 9, 1, 4, 2 ], to!string(b));
+    }
+}
+
+@system unittest
+{
+    // Test range interface.
+    import std.algorithm.comparison : equal;
+    int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
+    auto h = heapify(a);
+    static assert(isInputRange!(typeof(h)));
+    assert(h.equal([16, 14, 10, 9, 8, 7, 4, 3, 2, 1]));
+}
+
+@system unittest // 15675
+{
+    import std.container.array : Array;
+
+    Array!int elements = [1, 2, 10, 12];
+    auto heap = heapify(elements);
+    assert(heap.front == 12);
+}
+
+@system unittest // 16072
+{
+    auto q = heapify!"a > b"([2, 4, 5]);
+    q.insert(1);
+    q.insert(6);
+    assert(q.front == 1);
+
+    // test more multiple grows
+    int[] arr;
+    auto r = heapify!"a < b"(arr);
+    foreach (i; 0 .. 100)
+        r.insert(i);
+
+    assert(r.front == 99);
+}
+
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    int[] a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7];
+    auto heap = heapify(a);
+    auto dup = heap.dup();
+    assert(dup.equal([16, 14, 10, 9, 8, 7, 4, 3, 2, 1]));
+}
+
+@safe unittest
+{
+    static struct StructWithoutDup
+    {
+        int[] a;
+        @disable StructWithoutDup dup()
+        {
+            StructWithoutDup d;
+            return d;
+        }
+        alias a this;
+    }
+
+    // Assert Binary heap can be created when Store doesn't have dup
+    // if dup is not used.
+    assert(__traits(compiles, ()
+        {
+            auto s = StructWithoutDup([1,2]);
+            auto h = heapify(s);
+        }));
+
+    // Assert dup can't be used on BinaryHeaps when Store doesn't have dup
+    assert(!__traits(compiles, ()
+        {
+            auto s = StructWithoutDup([1,2]);
+            auto h = heapify(s);
+            h.dup();
+        }));
+}
+
+@safe unittest
+{
+    static struct StructWithDup
+    {
+        int[] a;
+        StructWithDup dup()
+        {
+            StructWithDup d;
+            return d;
+        }
+        alias a this;
+    }
+
+    // Assert dup can be used on BinaryHeaps when Store has dup
+    assert(__traits(compiles, ()
+        {
+            auto s = StructWithDup([1, 2]);
+            auto h = heapify(s);
+            h.dup();
+        }));
+}
+
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.internal.test.dummyrange;
+
+    alias RefRange = DummyRange!(ReturnBy.Reference, Length.Yes, RangeType.Random);
+
+    RefRange a;
+    RefRange b;
+    a.reinit();
+    b.reinit();
+
+    auto heap = heapify(a);
+    foreach (ref elem; b)
+    {
+        heap.conditionalSwap(elem);
+    }
+
+    assert(equal(heap, [ 5, 5, 4, 4, 3, 3, 2, 2, 1, 1]));
+    assert(equal(b, [10, 9, 8, 7, 6, 6, 7, 8, 9, 10]));
+}
+
+@system unittest // Issue 17314
+{
+    import std.algorithm.comparison : equal;
+    int[] a = [5];
+    auto heap = heapify(a);
+    heap.insert(6);
+    assert(equal(heap, [6, 5]));
+}