d: Import dmd b8384668f, druntime e6caaab9, phobos 5ab9ad256 (v2.098.0-beta.1)

The D front-end is now itself written in D, in order to build GDC, you will need a working GDC compiler (GCC version 9.1 or later). GCC changes: - Add support for bootstrapping the D front-end. These add the required components in order to have a D front-end written in D itself. Because the compiler front-end only depends on the core runtime modules, only libdruntime is built for the bootstrap stages. D front-end changes: - Import dmd v2.098.0-beta.1. Druntime changes: - Import druntime v2.098.0-beta.1. Phobos changes: - Import phobos v2.098.0-beta.1. The jump from v2.076.1 to v2.098.0 covers nearly 4 years worth of development on the D programming language and run-time libraries. ChangeLog: * Makefile.def: Add bootstrap to libbacktrace, libphobos, zlib, and libatomic. * Makefile.in: Regenerate. * Makefile.tpl (POSTSTAGE1_HOST_EXPORTS): Fix command for GDC. (STAGE1_CONFIGURE_FLAGS): Add --with-libphobos-druntime-only if target-libphobos-bootstrap. (STAGE2_CONFIGURE_FLAGS): Likewise. * configure: Regenerate. * configure.ac: Add support for bootstrapping D front-end. config/ChangeLog: * acx.m4 (ACX_PROG_GDC): New m4 function. gcc/ChangeLog: * Makefile.in (GDC): New variable. (GDCFLAGS): New variable. * configure: Regenerate. * configure.ac: Add call to ACX_PROG_GDC. Substitute GDCFLAGS. gcc/d/ChangeLog: * dmd/MERGE: Merge upstream dmd b8384668f. * Make-lang.in (d-warn): Use strict warnings. (DMD_WARN_CXXFLAGS): Remove. (DMD_COMPILE): Remove. (CHECKING_DFLAGS): Define. (WARN_DFLAGS): Define. (ALL_DFLAGS): Define. (DCOMPILE.base): Define. (DCOMPILE): Define. (DPOSTCOMPILE): Define. (DLINKER): Define. (DLLINKER): Define. (D_FRONTEND_OBJS): Add new dmd front-end objects. (D_GENERATED_SRCS): Remove. (D_GENERATED_OBJS): Remove. (D_ALL_OBJS): Remove D_GENERATED_OBJS. (d21$(exeext)): Build using DLLINKER and -static-libphobos. (d.tags): Remove dmd/*.c and dmd/root/*.c. (d.mostlyclean): Remove D_GENERATED_SRCS, d/idgen$(build_exeext), d/impcnvgen$(build_exeext). (D_INCLUDES): Include $(srcdir)/d/dmd/res. (CFLAGS-d/id.o): Remove. (CFLAGS-d/impcnvtab.o): Remove. (d/%.o): Build using DCOMPILE and DPOSTCOMPILE. Update dependencies from d/dmd/%.c to d/dmd/%.d. (d/idgen$(build_exeext)): Remove. (d/impcnvgen$(build_exeext)): Remove. (d/id.c): Remove. (d/id.h): Remove. (d/impcnvtab.c): Remove. (d/%.dmdgen.o): Remove. (D_SYSTEM_H): Remove. (d/idgen.dmdgen.o): Remove. (d/impcnvgen.dmdgen.o): Remove. * config-lang.in (boot_language): New variable. * d-attribs.cc: Include dmd/expression.h. * d-builtins.cc: Include d-frontend.h. (build_frontend_type): Update for new front-end interface. (d_eval_constant_expression): Likewise. (d_build_builtins_module): Likewise. (maybe_set_builtin_1): Likewise. (d_build_d_type_nodes): Likewise. * d-codegen.cc (d_decl_context): Likewise. (declaration_reference_p): Likewise. (declaration_type): Likewise. (parameter_reference_p): Likewise. (parameter_type): Likewise. (get_array_length): Likewise. (build_delegate_cst): Likewise. (build_typeof_null_value): Likewise. (identity_compare_p): Likewise. (lower_struct_comparison): Likewise. (build_filename_from_loc): Likewise. (build_assert_call): Remove LIBCALL_SWITCH_ERROR. (build_bounds_index_condition): Call LIBCALL_ARRAYBOUNDS_INDEXP on bounds error. (build_bounds_slice_condition): Call LIBCALL_ARRAYBOUNDS_SLICEP on bounds error. (array_bounds_check): Update for new front-end interface. (checkaction_trap_p): Handle CHECKACTION_context. (get_function_type): Update for new front-end interface. (d_build_call): Likewise. * d-compiler.cc: Remove include of dmd/scope.h. (Compiler::genCmain): Remove. (Compiler::paintAsType): Update for new front-end interface. (Compiler::onParseModule): Likewise. * d-convert.cc (convert_expr): Remove call to LIBCALL_ARRAYCAST. (convert_for_rvalue): Update for new front-end interface. (convert_for_assignment): Likewise. (convert_for_condition): Likewise. (d_array_convert): Likewise. * d-diagnostic.cc (error): Remove. (errorSupplemental): Remove. (warning): Remove. (warningSupplemental): Remove. (deprecation): Remove. (deprecationSupplemental): Remove. (message): Remove. (vtip): New. * d-frontend.cc (global): Remove. (Global::_init): Remove. (Global::startGagging): Remove. (Global::endGagging): Remove. (Global::increaseErrorCount): Remove. (Loc::Loc): Remove. (Loc::toChars): Remove. (Loc::equals): Remove. (isBuiltin): Update for new front-end interface. (eval_builtin): Likewise. (getTypeInfoType): Likewise. (inlineCopy): Remove. * d-incpath.cc: Include d-frontend.h. (add_globalpaths): Call d_gc_malloc to allocate Strings. (add_filepaths): Likewise. * d-lang.cc: Include dmd/id.h, dmd/root/file.h, d-frontend.h. Remove include of dmd/mars.h, id.h. (entrypoint_module): Remove. (entrypoint_root_module): Remove. (deps_write_string): Update for new front-end interface. (deps_write): Likewise. (d_init_options): Call rt_init. Remove setting global params that are default initialized by the front-end. (d_handle_option): Handle OPT_fcheckaction_, OPT_fdump_c___spec_, OPT_fdump_c___spec_verbose, OPT_fextern_std_, OPT_fpreview, OPT_revert, OPT_fsave_mixins_, and OPT_ftransition. (d_post_options): Propagate dip1021 and dip1000 preview flags to dip25, and flag_diagnostics_show_caret to printErrorContext. (d_add_entrypoint_module): Remove. (d_parse_file): Update for new front-end interface. (d_type_promotes_to): Likewise. (d_types_compatible_p): Likewise. * d-longdouble.cc (CTFloat::zero): Remove. (CTFloat::one): Remove. (CTFloat::minusone): Remove. (CTFloat::half): Remove. * d-system.h (POSIX): Remove. (realpath): Remove. (isalpha): Remove. (isalnum): Remove. (isdigit): Remove. (islower): Remove. (isprint): Remove. (isspace): Remove. (isupper): Remove. (isxdigit): Remove. (tolower): Remove. (_mkdir): Remove. (INT32_MAX): Remove. (INT32_MIN): Remove. (INT64_MIN): Remove. (UINT32_MAX): Remove. (UINT64_MAX): Remove. * d-target.cc: Include calls.h. (target): Remove. (define_float_constants): Remove initialization of snan. (Target::_init): Update for new front-end interface. (Target::isVectorTypeSupported): Likewise. (Target::isVectorOpSupported): Remove cases for unordered operators. (TargetCPP::typeMangle): Update for new front-end interface. (TargetCPP::parameterType): Likewise. (Target::systemLinkage): Likewise. (Target::isReturnOnStack): Likewise. (Target::isCalleeDestroyingArgs): Define. (Target::preferPassByRef): Define. * d-tree.h (d_add_entrypoint_module): Remove. * decl.cc (gcc_attribute_p): Update for new front-end interface. (apply_pragma_crt): Define. (DeclVisitor::visit(PragmaDeclaration *)): Handle pragmas crt_constructor and crt_destructor. (DeclVisitor::visit(TemplateDeclaration *)): Update for new front-end interface. (DeclVisitor::visit): Likewise. (DeclVisitor::finish_vtable): Likewise. (get_symbol_decl): Error if template has more than one nesting context. Update for new front-end interface. (make_thunk): Update for new front-end interface. (get_vtable_decl): Likewise. * expr.cc (ExprVisitor::visit): Likewise. (build_return_dtor): Likewise. * imports.cc (ImportVisitor::visit): Likewise. * intrinsics.cc: Include dmd/expression.h. Remove include of dmd/mangle.h. (maybe_set_intrinsic): Update for new front-end interface. * intrinsics.def (INTRINSIC_ROL): Update intrinsic signature. (INTRINSIC_ROR): Likewise. (INTRINSIC_ROR_TIARG): Likewise. (INTRINSIC_TOPREC): Likewise. (INTRINSIC_TOPRECL): Likewise. (INTRINSIC_TAN): Update intrinsic module and signature. (INTRINSIC_ISNAN): Likewise. (INTRINSIC_ISFINITE): Likewise. (INTRINSIC_COPYSIGN): Define intrinsic. (INTRINSIC_COPYSIGNI): Define intrinsic. (INTRINSIC_EXP): Update intrinsic module. (INTRINSIC_EXPM1): Likewise. (INTRINSIC_EXP2): Likewise. (INTRINSIC_LOG): Likewise. (INTRINSIC_LOG2): Likewise. (INTRINSIC_LOG10): Likewise. (INTRINSIC_POW): Likewise. (INTRINSIC_ROUND): Likewise. (INTRINSIC_FLOORF): Likewise. (INTRINSIC_FLOOR): Likewise. (INTRINSIC_FLOORL): Likewise. (INTRINSIC_CEILF): Likewise. (INTRINSIC_CEIL): Likewise. (INTRINSIC_CEILL): Likewise. (INTRINSIC_TRUNC): Likewise. (INTRINSIC_FMIN): Likewise. (INTRINSIC_FMAX): Likewise. (INTRINSIC_FMA): Likewise. (INTRINSIC_VA_ARG): Update intrinsic signature. (INTRINSIC_VASTART): Likewise. * lang.opt (fcheck=): Add alternate aliases for contract switches. (fcheckaction=): New option. (check_action): New Enum and EnumValue entries. (fdump-c++-spec-verbose): New option. (fdump-c++-spec=): New option. (fextern-std=): New option. (extern_stdcpp): New Enum and EnumValue entries (fpreview=): New options. (frevert=): New options. (fsave-mixins): New option. (ftransition=): Update options. * modules.cc (get_internal_fn): Replace Prot with Visibility. (build_internal_fn): Likewise. (build_dso_cdtor_fn): Likewise. (build_module_tree): Remove check for __entrypoint module. * runtime.def (P5): Define. (ARRAYBOUNDS_SLICEP): Define. (ARRAYBOUNDS_INDEXP): Define. (NEWTHROW): Define. (ADCMP2): Remove. (ARRAYCAST): Remove. (SWITCH_STRING): Remove. (SWITCH_USTRING): Remove. (SWITCH_DSTRING): Remove. (SWITCH_ERROR): Remove. * toir.cc (IRVisitor::visit): Update for new front-end interface. (IRVisitor::check_previous_goto): Remove checks for case and default statements. (IRVisitor::visit(SwitchStatement *)): Remove handling of string switch conditions. * typeinfo.cc: Include d-frontend.h. (get_typeinfo_kind): Update for new front-end interface. (make_frontend_typeinfo): Likewise. (TypeInfoVisitor::visit): Likewise. (builtin_typeinfo_p): Likewise. (get_typeinfo_decl): Likewise. (build_typeinfo): Likewise. * types.cc (valist_array_p): Likewise. (make_array_type): Likewise. (merge_aggregate_types): Likewise. (TypeVisitor::visit(TypeBasic *)): Likewise. (TypeVisitor::visit(TypeFunction *)): Likewise. (TypeVisitor::visit(TypeStruct *)): Update comment. * verstr.h: Removed. * d-frontend.h: New file. gcc/po/ChangeLog: * EXCLUDES: Remove d/dmd sources from list. gcc/testsuite/ChangeLog: * gdc.dg/Wcastresult2.d: Update test. * gdc.dg/asm1.d: Likewise. * gdc.dg/asm2.d: Likewise. * gdc.dg/asm3.d: Likewise. * gdc.dg/gdc282.d: Likewise. * gdc.dg/imports/gdc170.d: Likewise. * gdc.dg/intrinsics.d: Likewise. * gdc.dg/pr101672.d: Likewise. * gdc.dg/pr90650a.d: Likewise. * gdc.dg/pr90650b.d: Likewise. * gdc.dg/pr94777a.d: Likewise. * gdc.dg/pr95250.d: Likewise. * gdc.dg/pr96869.d: Likewise. * gdc.dg/pr98277.d: Likewise. * gdc.dg/pr98457.d: Likewise. * gdc.dg/simd1.d: Likewise. * gdc.dg/simd2a.d: Likewise. * gdc.dg/simd2b.d: Likewise. * gdc.dg/simd2c.d: Likewise. * gdc.dg/simd2d.d: Likewise. * gdc.dg/simd2e.d: Likewise. * gdc.dg/simd2f.d: Likewise. * gdc.dg/simd2g.d: Likewise. * gdc.dg/simd2h.d: Likewise. * gdc.dg/simd2i.d: Likewise. * gdc.dg/simd2j.d: Likewise. * gdc.dg/simd7951.d: Likewise. * gdc.dg/torture/gdc309.d: Likewise. * gdc.dg/torture/pr94424.d: Likewise. * gdc.dg/torture/pr94777b.d: Likewise. * lib/gdc-utils.exp (gdc-convert-args): Handle new compiler options. (gdc-convert-test): Handle CXXFLAGS, EXTRA_OBJC_SOURCES, and ARG_SETS test directives. (gdc-do-test): Only import modules in the test run directory. * gdc.dg/pr94777c.d: New test. * gdc.dg/pr96156b.d: New test. * gdc.dg/pr96157c.d: New test. * gdc.dg/simd_ctfe.d: New test. * gdc.dg/torture/simd17344.d: New test. * gdc.dg/torture/simd20052.d: New test. * gdc.dg/torture/simd6.d: New test. * gdc.dg/torture/simd7.d: New test. libphobos/ChangeLog: * libdruntime/MERGE: Merge upstream druntime e6caaab9. * libdruntime/Makefile.am (D_EXTRA_FLAGS): Build libdruntime with -fpreview=dip1000, -fpreview=fieldwise, and -fpreview=dtorfields. (ALL_DRUNTIME_SOURCES): Add DRUNTIME_DSOURCES_STDCXX. (DRUNTIME_DSOURCES): Update list of C binding modules. (DRUNTIME_DSOURCES_STDCXX): Likewise. (DRUNTIME_DSOURCES_LINUX): Likewise. (DRUNTIME_DSOURCES_OPENBSD): Likewise. (DRUNTIME_DISOURCES): Remove __entrypoint.di. * libdruntime/Makefile.in: Regenerated. * libdruntime/__entrypoint.di: Removed. * libdruntime/gcc/deh.d (_d_isbaseof): Update signature. (_d_createTrace): Likewise. (__gdc_begin_catch): Remove reference to the exception. (_d_throw): Increment reference count of thrown object before unwind. (__gdc_personality): Chain exceptions with Throwable.chainTogether. * libdruntime/gcc/emutls.d: Update imports. * libdruntime/gcc/sections/elf.d: Update imports. (DSO.moduleGroup): Update signature. * libdruntime/gcc/sections/macho.d: Update imports. (DSO.moduleGroup): Update signature. * libdruntime/gcc/sections/pecoff.d: Update imports. (DSO.moduleGroup): Update signature. * src/MERGE: Merge upstream phobos 5ab9ad256. * src/Makefile.am (D_EXTRA_DFLAGS): Add -fpreview=dip1000 and -fpreview=dtorfields flags. (PHOBOS_DSOURCES): Update list of std modules. * src/Makefile.in: Regenerate. * testsuite/lib/libphobos.exp (libphobos-dg-test): Handle assembly compile types. (dg-test): Override. (additional_prunes): Define. (libphobos-dg-prune): Filter any additional_prunes set by tests. * testsuite/libphobos.aa/test_aa.d: Update test. * testsuite/libphobos.druntime/druntime.exp (version_flags): Add -fversion=CoreUnittest. * testsuite/libphobos.druntime_shared/druntime_shared.exp (version_flags): Add -fversion=CoreUnittest -fversion=Shared. * testsuite/libphobos.exceptions/unknown_gc.d: Update test. * testsuite/libphobos.hash/test_hash.d: Update test. * testsuite/libphobos.phobos/phobos.exp (version_flags): Add -fversion=StdUnittest * testsuite/libphobos.phobos_shared/phobos_shared.exp (version_flags): Likewise. * testsuite/libphobos.shared/host.c: Update test. * testsuite/libphobos.shared/load.d: Update test. * testsuite/libphobos.shared/load_13414.d: Update test. * testsuite/libphobos.thread/fiber_guard_page.d: Update test. * testsuite/libphobos.thread/tlsgc_sections.d: Update test. * testsuite/testsuite_flags.in: Add -fpreview=dip1000 to --gdcflags. * testsuite/libphobos.shared/link_mod_collision.d: Removed. * testsuite/libphobos.shared/load_mod_collision.d: Removed. * testsuite/libphobos.betterc/betterc.exp: New test. * testsuite/libphobos.config/config.exp: New test. * testsuite/libphobos.gc/gc.exp: New test. * testsuite/libphobos.imports/imports.exp: New test. * testsuite/libphobos.lifetime/lifetime.exp: New test. * testsuite/libphobos.unittest/unittest.exp: New test.
author: Iain Buclaw <ibuclaw@gdcproject.org> 2019-06-18 20:42:10 +0200
committer: Iain Buclaw <ibuclaw@gdcproject.org> 2021-11-30 16:53:28 +0100
commit: 5fee5ec362f7a243f459e6378fd49dfc89dc9fb5 (patch)
tree: 61d1bdbca854a903c0860406f457f06b2040be7a /libphobos/src/std/algorithm/setops.d
parent: b3f60112edcb85b459e60f66c44a55138b1cef49 (diff)
download: gcc-5fee5ec362f7a243f459e6378fd49dfc89dc9fb5.zip
gcc-5fee5ec362f7a243f459e6378fd49dfc89dc9fb5.tar.gz
gcc-5fee5ec362f7a243f459e6378fd49dfc89dc9fb5.tar.bz2
1 files changed, 127 insertions, 71 deletions
diff --git a/libphobos/src/std/algorithm/setops.d b/libphobos/src/std/algorithm/setops.d
index 05a6e7e..ede1831 100644
--- a/libphobos/src/std/algorithm/setops.d
+++ b/libphobos/src/std/algorithm/setops.d
@@ -40,7 +40,7 @@ License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
 
 Authors: $(HTTP erdani.com, Andrei Alexandrescu)
 
-Source: $(PHOBOSSRC std/algorithm/_setops.d)
+Source: $(PHOBOSSRC std/algorithm/setops.d)
 
 Macros:
 T2=$(TR $(TDNW $(LREF $1)) $(TD $+))
@@ -49,19 +49,17 @@ module std.algorithm.setops;
 
 import std.range.primitives;
 
-// FIXME
-import std.functional; // : unaryFun, binaryFun;
+import std.functional : unaryFun, binaryFun;
 import std.traits;
-// FIXME
-import std.meta; // : AliasSeq, staticMap, allSatisfy, anySatisfy;
+import std.meta : AliasSeq, staticMap, allSatisfy, anySatisfy;
 
-import std.algorithm.sorting; // : Merge;
+import std.algorithm.sorting : Merge;
 import std.typecons : No;
 
 // cartesianProduct
 /**
 Lazily computes the Cartesian product of two or more ranges. The product is a
-_range of tuples of elements from each respective range.
+range of tuples of elements from each respective range.
 
 The conditions for the two-range case are as follows:
 
@@ -69,8 +67,8 @@ If both ranges are finite, then one must be (at least) a
 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives) and the
 other an $(REF_ALTTEXT input range, isInputRange, std,range,primitives).
 
-If one _range is infinite and the other finite, then the finite _range must
-be a forward _range, and the infinite range can be an input _range.
+If one range is infinite and the other finite, then the finite range must
+be a forward range, and the infinite range can be an input range.
 
 If both ranges are infinite, then both must be forward ranges.
 
@@ -348,7 +346,7 @@ if (!allSatisfy!(isForwardRange, R1, R2) ||
     }
 }
 
-// Issue 13091
+// https://issues.dlang.org/show_bug.cgi?id=13091
 pure nothrow @safe @nogc unittest
 {
     int[1] a = [1];
@@ -393,7 +391,7 @@ if (ranges.length >= 2 &&
             return mixin(algoFormat("tuple(%(current[%d].front%|,%))",
                                     iota(0, current.length)));
         }
-        void popFront()
+        void popFront() scope
         {
             foreach_reverse (i, ref r; current)
             {
@@ -406,25 +404,27 @@ if (ranges.length >= 2 &&
                     r = ranges[i].save; // rollover
             }
         }
-        @property Result save()
+        @property Result save() scope return
         {
             Result copy = this;
             foreach (i, r; ranges)
             {
-                copy.ranges[i] = r.save;
+                copy.ranges[i] = ranges[i].save;
                 copy.current[i] = current[i].save;
             }
             return copy;
         }
     }
-    static assert(isForwardRange!Result);
+    static assert(isForwardRange!Result, Result.stringof ~ " must be a forward"
+            ~ " range");
 
     return Result(ranges);
 }
 
+// cartesian product of empty ranges should be empty
+// https://issues.dlang.org/show_bug.cgi?id=10693
 @safe unittest
 {
-    // Issue 10693: cartesian product of empty ranges should be empty.
     int[] a, b, c, d, e;
     auto cprod = cartesianProduct(a,b,c,d,e);
     assert(cprod.empty);
@@ -446,9 +446,9 @@ if (ranges.length >= 2 &&
     assert(cprod.init.empty);
 }
 
+// https://issues.dlang.org/show_bug.cgi?id=13393
 @safe unittest
 {
-    // Issue 13393
     assert(!cartesianProduct([0],[0],[0]).save.empty);
 }
 
@@ -486,7 +486,7 @@ if (!allSatisfy!(isForwardRange, R1, R2, RR) ||
     assert(is(ElementType!(typeof(N3)) == Tuple!(size_t,size_t,size_t)));
 
     assert(canFind(N3, tuple(0, 27, 7)));
-    assert(canFind(N3, tuple(50, 23, 71)));
+    assert(canFind(N3, tuple(50, 23, 11)));
     assert(canFind(N3, tuple(9, 3, 0)));
 }
 
@@ -504,10 +504,10 @@ if (!allSatisfy!(isForwardRange, R1, R2, RR) ||
 
     assert(canFind(N4, tuple(1, 2, 3, 4)));
     assert(canFind(N4, tuple(4, 3, 2, 1)));
-    assert(canFind(N4, tuple(10, 31, 7, 12)));
+    assert(canFind(N4, tuple(10, 3, 1, 2)));
 }
 
-// Issue 9878
+// https://issues.dlang.org/show_bug.cgi?id=9878
 ///
 @safe unittest
 {
@@ -546,7 +546,7 @@ pure @safe nothrow @nogc unittest
     assert(D.front == front1);
 }
 
-// Issue 13935
+// https://issues.dlang.org/show_bug.cgi?id=13935
 @safe unittest
 {
     import std.algorithm.iteration : map;
@@ -554,12 +554,46 @@ pure @safe nothrow @nogc unittest
     foreach (pair; cartesianProduct(seq, seq)) {}
 }
 
+@system unittest
+{
+    import std.algorithm.comparison : equal;
+    import std.typecons : tuple;
+
+    static struct SystemRange
+    {
+        int[] data;
+
+        int front() @system @property inout
+        {
+            return data[0];
+        }
+
+        bool empty() @system @property inout
+        {
+            return data.length == 0;
+        }
+
+        void popFront() @system
+        {
+            data = data[1 .. $];
+        }
+
+        SystemRange save() @system
+        {
+            return this;
+        }
+    }
+
+    assert(SystemRange([1, 2]).cartesianProduct(SystemRange([3, 4]))
+        .equal([tuple(1, 3), tuple(1, 4), tuple(2, 3), tuple(2, 4)]));
+}
+
 // largestPartialIntersection
 /**
 Given a range of sorted $(REF_ALTTEXT forward ranges, isForwardRange, std,range,primitives)
-$(D ror), copies to $(D tgt) the elements that are common to most ranges, along with their number
-of occurrences. All ranges in $(D ror) are assumed to be sorted by $(D
-less). Only the most frequent $(D tgt.length) elements are returned.
+`ror`, copies to `tgt` the elements that are common to most ranges, along with their number
+of occurrences. All ranges in `ror` are assumed to be sorted by $(D
+less). Only the most frequent `tgt.length` elements are returned.
 
 Params:
     less = The predicate the ranges are sorted by.
@@ -567,27 +601,27 @@ Params:
     tgt = The target range to copy common elements to.
     sorted = Whether the elements copied should be in sorted order.
 
-The function $(D largestPartialIntersection) is useful for
+The function `largestPartialIntersection` is useful for
 e.g. searching an $(LINK2 https://en.wikipedia.org/wiki/Inverted_index,
 inverted index) for the documents most
 likely to contain some terms of interest. The complexity of the search
-is $(BIGOH n * log(tgt.length)), where $(D n) is the sum of lengths of
+is $(BIGOH n * log(tgt.length)), where `n` is the sum of lengths of
 all input ranges. This approach is faster than keeping an associative
 array of the occurrences and then selecting its top items, and also
-requires less memory ($(D largestPartialIntersection) builds its
-result directly in $(D tgt) and requires no extra memory).
+requires less memory (`largestPartialIntersection` builds its
+result directly in `tgt` and requires no extra memory).
 
 If at least one of the ranges is a multiset, then all occurences
 of a duplicate element are taken into account. The result is
 equivalent to merging all ranges and picking the most frequent
-$(D tgt.length) elements.
+`tgt.length` elements.
 
-Warning: Because $(D largestPartialIntersection) does not allocate
-extra memory, it will leave $(D ror) modified. Namely, $(D
-largestPartialIntersection) assumes ownership of $(D ror) and
+Warning: Because `largestPartialIntersection` does not allocate
+extra memory, it will leave `ror` modified. Namely, $(D
+largestPartialIntersection) assumes ownership of `ror` and
 discretionarily swaps and advances elements of it. If you want $(D
 ror) to preserve its contents after the call, you may want to pass a
-duplicate to $(D largestPartialIntersection) (and perhaps cache the
+duplicate to `largestPartialIntersection` (and perhaps cache the
 duplicate in between calls).
  */
 void largestPartialIntersection
@@ -652,13 +686,13 @@ import std.algorithm.sorting : SortOutput; // FIXME
 
 // largestPartialIntersectionWeighted
 /**
-Similar to $(D largestPartialIntersection), but associates a weight
+Similar to `largestPartialIntersection`, but associates a weight
 with each distinct element in the intersection.
 
 If at least one of the ranges is a multiset, then all occurences
 of a duplicate element are taken into account. The result
 is equivalent to merging all input ranges and picking the highest
-$(D tgt.length), weight-based ranking elements.
+`tgt.length`, weight-based ranking elements.
 
 Params:
     less = The predicate the ranges are sorted by.
@@ -798,15 +832,15 @@ void largestPartialIntersectionWeighted
 Merges multiple sets. The input sets are passed as a
 range of ranges and each is assumed to be sorted by $(D
 less). Computation is done lazily, one union element at a time. The
-complexity of one $(D popFront) operation is $(BIGOH
-log(ror.length)). However, the length of $(D ror) decreases as ranges
+complexity of one `popFront` operation is $(BIGOH
+log(ror.length)). However, the length of `ror` decreases as ranges
 in it are exhausted, so the complexity of a full pass through $(D
 MultiwayMerge) is dependent on the distribution of the lengths of ranges
-contained within $(D ror). If all ranges have the same length $(D n)
+contained within `ror`. If all ranges have the same length `n`
 (worst case scenario), the complexity of a full pass through $(D
 MultiwayMerge) is $(BIGOH n * ror.length * log(ror.length)), i.e., $(D
 log(ror.length)) times worse than just spanning all ranges in
-turn. The output comes sorted (unstably) by $(D less).
+turn. The output comes sorted (unstably) by `less`.
 
 The length of the resulting range is the sum of all lengths of
 the ranges passed as input. This means that all elements (duplicates
@@ -824,12 +858,15 @@ Params:
 Returns:
     A range of the union of the ranges in `ror`.
 
-Warning: Because $(D MultiwayMerge) does not allocate extra memory, it
-will leave $(D ror) modified. Namely, $(D MultiwayMerge) assumes ownership
-of $(D ror) and discretionarily swaps and advances elements of it. If
-you want $(D ror) to preserve its contents after the call, you may
-want to pass a duplicate to $(D MultiwayMerge) (and perhaps cache the
+Warning: Because `MultiwayMerge` does not allocate extra memory, it
+will leave `ror` modified. Namely, `MultiwayMerge` assumes ownership
+of `ror` and discretionarily swaps and advances elements of it. If
+you want `ror` to preserve its contents after the call, you may
+want to pass a duplicate to `MultiwayMerge` (and perhaps cache the
 duplicate in between calls).
+
+See_Also: $(REF merge, std,algorithm,sorting) for an analogous function that
+    takes a static number of ranges of possibly disparate types.
  */
 struct MultiwayMerge(alias less, RangeOfRanges)
 {
@@ -883,7 +920,8 @@ struct MultiwayMerge(alias less, RangeOfRanges)
             return;
         }
         // Put the popped range back in the heap
-        _heap.conditionalInsert(_ror.back) || assert(false);
+        const bool worked = _heap.conditionalInsert(_ror.back);
+        assert(worked, "Failed to insert item into heap");
     }
 }
 
@@ -930,7 +968,8 @@ alias nWayUnion = multiwayMerge;
 alias NWayUnion = MultiwayMerge;
 
 /**
-Computes the union of multiple ranges. The input ranges are passed
+Computes the union of multiple ranges. The
+$(REF_ALTTEXT input ranges, isInputRange, std,range,primitives) are passed
 as a range of ranges and each is assumed to be sorted by $(D
 less). Computation is done lazily, one union element at a time.
 `multiwayUnion(ror)` is functionally equivalent to `multiwayMerge(ror).uniq`.
@@ -949,7 +988,8 @@ See also: $(LREF multiwayMerge)
 auto multiwayUnion(alias less = "a < b", RangeOfRanges)(RangeOfRanges ror)
 {
     import std.algorithm.iteration : uniq;
-    return ror.multiwayMerge.uniq;
+    import std.functional : not;
+    return ror.multiwayMerge!(less).uniq!(not!less);
 }
 
 ///
@@ -980,17 +1020,26 @@ auto multiwayUnion(alias less = "a < b", RangeOfRanges)(RangeOfRanges ror)
         [ 7 ],
     ];
     assert(equal(multiwayUnion(b), witness));
+
+    double[][] c =
+    [
+        [9, 8, 8, 8, 7, 6],
+        [9, 8, 6],
+        [9, 8, 5]
+    ];
+    auto witness2 = [9, 8, 7, 6, 5];
+    assert(equal(multiwayUnion!"a > b"(c), witness2));
 }
 
 /**
-Lazily computes the difference of $(D r1) and $(D r2). The two ranges
-are assumed to be sorted by $(D less). The element types of the two
+Lazily computes the difference of `r1` and `r2`. The two ranges
+are assumed to be sorted by `less`. The element types of the two
 ranges must have a common type.
 
 
 In the case of multisets, considering that element `a` appears `x`
-times in $(D r1) and `y` times and $(D r2), the number of occurences
-of `a` in the resulting range is going to be `x-y` if x > y or 0 othwerise.
+times in `r1` and `y` times and `r2`, the number of occurences
+of `a` in the resulting range is going to be `x-y` if x > y or 0 otherwise.
 
 Params:
     less = Predicate the given ranges are sorted by.
@@ -1048,7 +1097,7 @@ public:
     ///
     @property auto ref front()
     {
-        assert(!empty);
+        assert(!empty, "Can not get front of empty SetDifference");
         return r1.front;
     }
 
@@ -1095,7 +1144,8 @@ SetDifference!(less, R1, R2) setDifference(alias less = "a < b", R1, R2)
     assert(setDifference(r, x).empty);
 }
 
-@safe unittest // Issue 10460
+// https://issues.dlang.org/show_bug.cgi?id=10460
+@safe unittest
 {
     import std.algorithm.comparison : equal;
 
@@ -1107,8 +1157,9 @@ SetDifference!(less, R1, R2) setDifference(alias less = "a < b", R1, R2)
 }
 
 /**
-Lazily computes the intersection of two or more input ranges $(D
-ranges). The ranges are assumed to be sorted by $(D less). The element
+Lazily computes the intersection of two or more
+$(REF_ALTTEXT input ranges, isInputRange, std,range,primitives)
+`ranges`. The ranges are assumed to be sorted by `less`. The element
 types of the ranges must have a common type.
 
 In the case of multisets, the range with the minimum number of
@@ -1179,11 +1230,12 @@ public:
     ///
     void popFront()
     {
-        assert(!empty);
+        assert(!empty, "Can not popFront of empty SetIntersection");
         static if (Rs.length > 1) foreach (i, ref r; _input)
         {
             alias next = _input[(i + 1) % Rs.length];
-            assert(!comp(r.front, next.front));
+            assert(!comp(r.front, next.front), "Set elements must not"
+                    ~ " contradict the less predicate");
         }
 
         foreach (ref r; _input)
@@ -1196,7 +1248,7 @@ public:
     ///
     @property ElementType front()
     {
-        assert(!empty);
+        assert(!empty, "Can not get front of empty SetIntersection");
         return _input[0].front;
     }
 
@@ -1274,20 +1326,20 @@ if (Rs.length >= 2 && allSatisfy!(isInputRange, Rs) &&
 }
 
 /**
-Lazily computes the symmetric difference of $(D r1) and $(D r2),
-i.e. the elements that are present in exactly one of $(D r1) and $(D
-r2). The two ranges are assumed to be sorted by $(D less), and the
-output is also sorted by $(D less). The element types of the two
+Lazily computes the symmetric difference of `r1` and `r2`,
+i.e. the elements that are present in exactly one of `r1` and $(D
+r2). The two ranges are assumed to be sorted by `less`, and the
+output is also sorted by `less`. The element types of the two
 ranges must have a common type.
 
 If both ranges are sets (without duplicated elements), the resulting
 range is going to be a set. If at least one of the ranges is a multiset,
 the number of occurences of an element `x` in the resulting range is `abs(a-b)`
-where `a` is the number of occurences of `x` in $(D r1), `b` is the number of
-occurences of `x` in $(D r2), and `abs` is the absolute value.
+where `a` is the number of occurences of `x` in `r1`, `b` is the number of
+occurences of `x` in `r2`, and `abs` is the absolute value.
 
 If both arguments are ranges of L-values of the same type then
-$(D SetSymmetricDifference) will also be a range of L-values of
+`SetSymmetricDifference` will also be a range of L-values of
 that type.
 
 Params:
@@ -1336,7 +1388,7 @@ public:
     ///
     void popFront()
     {
-        assert(!empty);
+        assert(!empty, "Can not popFront of empty SetSymmetricDifference");
         if (r1.empty) r2.popFront();
         else if (r2.empty) r1.popFront();
         else
@@ -1348,7 +1400,8 @@ public:
             }
             else
             {
-                assert(comp(r2.front, r1.front));
+                assert(comp(r2.front, r1.front), "Elements of R1 and R2"
+                        ~ " must be different");
                 r2.popFront();
             }
         }
@@ -1358,9 +1411,11 @@ public:
     ///
     @property auto ref front()
     {
-        assert(!empty);
+        assert(!empty, "Can not get the front of an empty"
+                ~ " SetSymmetricDifference");
         immutable chooseR1 = r2.empty || !r1.empty && comp(r1.front, r2.front);
-        assert(chooseR1 || r1.empty || comp(r2.front, r1.front));
+        assert(chooseR1 || r1.empty || comp(r2.front, r1.front), "Failed to"
+                ~ " get appropriate front");
         return chooseR1 ? r1.front : r2.front;
     }
 
@@ -1410,7 +1465,8 @@ setSymmetricDifference(alias less = "a < b", R1, R2)
     assert(equal(setSymmetricDifference(c, d), [1, 1, 2, 5, 6, 7, 9]));
 }
 
-@safe unittest // Issue 10460
+// https://issues.dlang.org/show_bug.cgi?id=10460
+@safe unittest
 {
     import std.algorithm.comparison : equal;
 
@@ -1435,8 +1491,8 @@ TODO: once SetUnion got deprecated we can provide the usual definition
 (= merge + filter after uniqs)
 See: https://github.com/dlang/phobos/pull/4249
 /**
-Lazily computes the union of two or more ranges $(D rs). The ranges
-are assumed to be sorted by $(D less). Elements in the output are
+Lazily computes the union of two or more ranges `rs`. The ranges
+are assumed to be sorted by `less`. Elements in the output are
 unique. The element types of all ranges must have a common type.
 
 Params:
author	Iain Buclaw <ibuclaw@gdcproject.org>	2019-06-18 20:42:10 +0200
committer	Iain Buclaw <ibuclaw@gdcproject.org>	2021-11-30 16:53:28 +0100
commit	5fee5ec362f7a243f459e6378fd49dfc89dc9fb5 (patch)
tree	61d1bdbca854a903c0860406f457f06b2040be7a /libphobos/src/std/algorithm/setops.d
parent	b3f60112edcb85b459e60f66c44a55138b1cef49 (diff)
download	gcc-5fee5ec362f7a243f459e6378fd49dfc89dc9fb5.zip gcc-5fee5ec362f7a243f459e6378fd49dfc89dc9fb5.tar.gz gcc-5fee5ec362f7a243f459e6378fd49dfc89dc9fb5.tar.bz2