aboutsummaryrefslogtreecommitdiff
path: root/libphobos/src/std/algorithm
diff options
context:
space:
mode:
authorIain Buclaw <ibuclaw@gdcproject.org>2023-03-05 01:47:19 +0100
committerIain Buclaw <ibuclaw@gdcproject.org>2023-03-16 17:29:57 +0100
commit8da8c7d337123b28fdeb539a283d00732118712e (patch)
tree74096a23b9e2f64a7e25ec1e8d4d3b1d8934842e /libphobos/src/std/algorithm
parentc5e2c3dd6afcf9b152df72b30e205b0180c0afd5 (diff)
downloadgcc-8da8c7d337123b28fdeb539a283d00732118712e.zip
gcc-8da8c7d337123b28fdeb539a283d00732118712e.tar.gz
gcc-8da8c7d337123b28fdeb539a283d00732118712e.tar.bz2
d: Merge upstream dmd, druntime 4ca4140e58, phobos 454dff14d.
D front-end changes: - Import dmd v2.103.0-beta.1. - Using `alias this' for classes has been deprecated. - The feature `-fpreview=dip25` is now enabled by default. - The compile-time traits `isVirtualFunction' and `getVirtualFunctions' have been deprecated. D runtime changes: - Import druntime v2.103.0-beta.1. Phobos changes: - Import phobos v2.103.0-beta.1. - Updated unicode grapheme walking updated to conform to Unicode version 15. - Improved friendliness of error messages when instantiating `std.algorithm.iteration.joiner' and `std.algorithm.sorting.sort' with wrong inputs. gcc/d/ChangeLog: * dmd/MERGE: Merge upstream dmd 4ca4140e58. * dmd/VERSION: Bump version to v2.103.0-beta.1. * Make-lang.in (D_FRONTEND_OBJS): Add d/errorsink.o. * d-ctfloat.cc (CTFloat::sprint): Update signature for new front-end interface. * d-frontend.cc (getTypeInfoType): Likewise. * d-lang.cc (d_handle_option): Remove handling of -fpreview=dip25 and -frevert=dip25. (d_post_options): Remove enabling of sealed references language feature when scoped pointers is enabled. * d-tree.h (create_typeinfo): Update signature. * decl.cc (DeclVisitor::finish_vtable): Update for new front-end interface. (DeclVisitor::visit (VarDeclaration *)): Likewise. (DeclVisitor::visit (FuncDeclaration *)): Check skipCodegen to see if front-end explicitly requested not to generate code. * expr.cc (ExprVisitor::visit (NewExp *)): Update for new front-end interface. * lang.opt (fpreview=dip25): Remove. (frevert=dip25): Remove. * modules.cc (layout_moduleinfo_fields): Update for new front-end interface. (layout_moduleinfo): Likewise. * runtime.def (NEWCLASS): Remove. * toir.cc (IRVisitor::visit (IfStatement *)): Don't generate IR for if statement list when condition is `__ctfe'. * typeinfo.cc (create_typeinfo): Add generate parameter. * types.cc (layout_aggregate_members): Update for new front-end interface. libphobos/ChangeLog: * libdruntime/MERGE: Merge upstream druntime 4ca4140e58. * libdruntime/Makefile.am (DRUNTIME_DSOURCES): Add core/factory.d. * libdruntime/Makefile.in: Regenerate. * src/MERGE: Merge upstream phobos 454dff14d. * testsuite/libphobos.hash/test_hash.d: Update test. * testsuite/libphobos.shared/finalize.d: Update test. * libdruntime/core/factory.d: New file. gcc/testsuite/ChangeLog: * gdc.dg/torture/simd23084.d: New test. * gdc.dg/torture/simd23085.d: New test. * gdc.dg/torture/simd23218.d: New test.
Diffstat (limited to 'libphobos/src/std/algorithm')
-rw-r--r--libphobos/src/std/algorithm/iteration.d20
-rw-r--r--libphobos/src/std/algorithm/package.d1
-rw-r--r--libphobos/src/std/algorithm/sorting.d79
3 files changed, 77 insertions, 23 deletions
diff --git a/libphobos/src/std/algorithm/iteration.d b/libphobos/src/std/algorithm/iteration.d
index 967d2a6..8236076 100644
--- a/libphobos/src/std/algorithm/iteration.d
+++ b/libphobos/src/std/algorithm/iteration.d
@@ -2969,10 +2969,24 @@ iterated from the back to the front, the separator will still be consumed from
front to back, even if it is a bidirectional range too.
*/
auto joiner(RoR, Separator)(RoR r, Separator sep)
-if (isInputRange!RoR && isInputRange!(ElementType!RoR)
- && isForwardRange!Separator
- && is(ElementType!Separator : ElementType!(ElementType!RoR)))
{
+ static assert(isInputRange!RoR, "The type of RoR '", RoR.stringof
+ , " must be an InputRange (isInputRange!", RoR.stringof, ").");
+ static assert(isInputRange!(ElementType!RoR), "The ElementyType of RoR '"
+ , ElementType!(RoR).stringof, "' must be an InputRange "
+ , "(isInputRange!(ElementType!(", RoR.stringof , "))).");
+ static assert(isForwardRange!Separator, "The type of the Seperator '"
+ , Seperator.stringof, "' must be a ForwardRange (isForwardRange!("
+ , Seperator.stringof, ")).");
+ static assert(is(ElementType!Separator : ElementType!(ElementType!RoR))
+ , "The type of the elements of the separator range does not match "
+ , "the type of the elements that are joined. Separator type '"
+ , ElementType!(Separator).stringof, "' is not implicitly"
+ , "convertible to range element type '"
+ , ElementType!(ElementType!RoR).stringof, "' (is(ElementType!"
+ , Separator.stringof, " : ElementType!(ElementType!", RoR.stringof
+ , "))).");
+
static struct Result
{
private RoR _items;
diff --git a/libphobos/src/std/algorithm/package.d b/libphobos/src/std/algorithm/package.d
index 6aacd51..71bd1d9 100644
--- a/libphobos/src/std/algorithm/package.d
+++ b/libphobos/src/std/algorithm/package.d
@@ -103,6 +103,7 @@ $(TR
$(SUBREF sorting, multiSort)
$(SUBREF sorting, nextEvenPermutation)
$(SUBREF sorting, nextPermutation)
+ $(SUBREF sorting, nthPermutation)
$(SUBREF sorting, partialSort)
$(SUBREF sorting, partition)
$(SUBREF sorting, partition3)
diff --git a/libphobos/src/std/algorithm/sorting.d b/libphobos/src/std/algorithm/sorting.d
index ddb80b8..c5b085d 100644
--- a/libphobos/src/std/algorithm/sorting.d
+++ b/libphobos/src/std/algorithm/sorting.d
@@ -1922,14 +1922,8 @@ See_Also:
$(REF binaryFun, std,functional)
*/
SortedRange!(Range, less)
-sort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable,
- Range)(Range r)
-if (((ss == SwapStrategy.unstable && (hasSwappableElements!Range ||
- hasAssignableElements!Range)) ||
- (ss != SwapStrategy.unstable && hasAssignableElements!Range)) &&
- isRandomAccessRange!Range &&
- hasSlicing!Range &&
- hasLength!Range)
+sort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)
+(Range r)
/+ Unstable sorting uses the quicksort algorithm, which uses swapAt,
which either uses swap(...), requiring swappable elements, or just
swaps using assignment.
@@ -1937,21 +1931,46 @@ if (((ss == SwapStrategy.unstable && (hasSwappableElements!Range ||
requiring assignable elements. +/
{
import std.range : assumeSorted;
- alias lessFun = binaryFun!(less);
- alias LessRet = typeof(lessFun(r.front, r.front)); // instantiate lessFun
- static if (is(LessRet == bool))
+ static if (ss == SwapStrategy.unstable)
{
- static if (ss == SwapStrategy.unstable)
- quickSortImpl!(lessFun)(r, r.length);
- else //use Tim Sort for semistable & stable
- TimSortImpl!(lessFun, Range).sort(r, null);
-
- assert(isSorted!lessFun(r), "Failed to sort range of type " ~ Range.stringof);
+ static assert(hasSwappableElements!Range || hasAssignableElements!Range,
+ "When using SwapStrategy.unstable, the passed Range '"
+ ~ Range.stringof ~ "' must"
+ ~ " either fulfill hasSwappableElements, or"
+ ~ " hasAssignableElements, both were not the case");
}
else
{
- static assert(false, "Invalid predicate passed to sort: " ~ less.stringof);
+ static assert(hasAssignableElements!Range, "When using a SwapStrategy"
+ ~ " != unstable, the"
+ ~ " passed Range '" ~ Range.stringof ~ "' must fulfill"
+ ~ " hasAssignableElements, which it did not");
}
+
+ static assert(isRandomAccessRange!Range, "The passed Range '"
+ ~ Range.stringof ~ "' must be a Random AccessRange "
+ ~ "(isRandomAccessRange)");
+
+ static assert(hasSlicing!Range, "The passed Range '"
+ ~ Range.stringof ~ "' must allow Slicing (hasSlicing)");
+
+ static assert(hasLength!Range, "The passed Range '"
+ ~ Range.stringof ~ "' must have a length (hasLength)");
+
+ alias lessFun = binaryFun!(less);
+ alias LessRet = typeof(lessFun(r.front, r.front)); // instantiate lessFun
+
+ static assert(is(LessRet == bool), "The return type of the template"
+ ~ " argument 'less' when used with the binaryFun!less template"
+ ~ " must be a bool. This is not the case, the returned type is '"
+ ~ LessRet.stringof ~ "'");
+
+ static if (ss == SwapStrategy.unstable)
+ quickSortImpl!(lessFun)(r, r.length);
+ else //use Tim Sort for semistable & stable
+ TimSortImpl!(lessFun, Range).sort(r, null);
+
+ assert(isSorted!lessFun(r), "Failed to sort range of type " ~ Range.stringof);
return assumeSorted!less(r);
}
@@ -2599,8 +2618,16 @@ private template TimSortImpl(alias pred, R)
//Test for overflow
if (newSize < minCapacity) newSize = minCapacity;
- if (__ctfe) temp.length = newSize;
- else temp = () @trusted { return uninitializedArray!(T[])(newSize); }();
+ // can't use `temp.length` if there's no default constructor
+ static if (__traits(compiles, { T defaultConstructed; cast(void) defaultConstructed; }))
+ {
+ if (__ctfe) temp.length = newSize;
+ else temp = () @trusted { return uninitializedArray!(T[])(newSize); }();
+ }
+ else
+ {
+ temp = () @trusted { return uninitializedArray!(T[])(newSize); }();
+ }
}
return temp;
}
@@ -3037,6 +3064,18 @@ private template TimSortImpl(alias pred, R)
sort!(cmp, SwapStrategy.stable)(makeArray(minMerge + 5));
}
+// https://issues.dlang.org/show_bug.cgi?id=23668
+@safe unittest
+{
+ static struct S
+ {
+ int opCmp(const S) const { return 1; }
+ @disable this();
+ }
+ S[] array;
+ array.sort!("a < b", SwapStrategy.stable);
+}
+
// schwartzSort
/**
Alternative sorting method that should be used when comparing keys involves an