Bug 9071 – sort function won't compile but Range fits describtion

The function sortImpl implies that the type returned by the slice operator of the passed range is of the same type. This must not be true. If it is not sortImpl will not instantiate recursively because of a type mismatch. This is a problem for custom container. (Currently I have this problem) To fix this. It should be checked whether or not the returned type of the opSlice funtion is of the same type as the original range. static assert(is(ReturnType!(Range.opSlice) == Range));

This is actually a problem with "hasSlicing": It is currently being tightened so that the result of a slice operation *must* be convertible back to the original type. If this is not the case, then the range will not be considered sliceable. Once this is deployed, you will (should) be forwarded to the "correct" overload of sortImpl: The one that doesn't use slicing. Still, could you please provide the code example that fails? This will help us figure out which of the following is the culprit: * The range? * The definition of hasSlicing? * The implementation of sort? And correctly address the issue.

where do you want the examples. it is pretty long 270 lines. The problem is a combination of the way opSlice doesn't require a specific return type and. the recursive nature of sortImpl and that sortImpl assigns slices. algorithm.d:7306 auto right = r[lessI + 1..r.length]; // here r is still of type Range // right is the return type of opSlice auto left = r[0..min(lessI, greaterI + 1)]; // same goes for left if (right.length > left.length) { swap(left, right); } .sortImpl!(less, ss, Range)(right); // here sortImpl calls itself where right is not of type Range r = left; // this assignment will fail because the assign operator of Range is not required to accept the return type of opSlice

(In reply to comment #2) > where do you want the examples. it is pretty long 270 lines. You can post it in dpaste: http://dpaste.dzfl.pl/new An added bonus is that it should show us the exact same compile error you are getting. > The problem is a > combination of the way opSlice doesn't require a specific return type and. the > recursive nature of sortImpl and that sortImpl assigns slices. > > > algorithm.d:7306 > auto right = r[lessI + 1..r.length]; // here r is still of type Range > // right is the return type of opSlice > auto left = r[0..min(lessI, greaterI + 1)]; // same goes for left > if (right.length > left.length) > { > swap(left, right); > } > .sortImpl!(less, ss, Range)(right); // here sortImpl calls itself where right > is not of type Range > r = left; // this assignment will fail because the assign operator of Range is > not required to accept the return type of opSlice I see. In that case, there is a bit of both issues. Please post your code, I'll take care of this issue.

http://dpaste.dzfl.pl/163a9600 prints the exact same error thanks

OK, what you showed me was that indeed, "deque" is not "sliceable" according to the new definition. It does also show that there are some issues in sort's implementation that need to be looked into. However (next section relevant), note that it is perfectly possible to sort your container via a slice of that container: http://dpaste.dzfl.pl/e601b75a I just added "opSlice();", and changed the call to: std.algorithm.sort!("a < b")(de[]); -------- On a side note, regarding your dequeue implementation: You are mixing the notion of container, and range. A container holds stuff. A range gives you an interface to access that stuff. The difference becomes apparent once you start poping stuff. A range is expected to merelly "walk forward", whereas your container will actually discard and destroy its elements: Not the expected behavior. This is especially true in your "save" implementation: Save is just supposed to duplicate the range (the view) itself, but not the elements. In particular, this should always hold (provided non-transisent assignable): Range r = something; auto rr = r.save; r.front = someValue; assert(rr.front == someValue); In your case, your implementation of "save" is what "dup" should be. Your save should probably be implemented as simply "return this"; Do you have a C++ background? It's kind of the same in the sense that you can't sort a container directly, but a pair of that container's iterator. Unless you have a Java background? Anyways, the "standard" fix is usually to just rename your "popFront" functions into "removeFront". -------- Last but not least (since I'm reviewing your implementation), it is usually considered an *error* to access past an empty range/iterator, or to access past the valid bounds of a container. It is usually recommended in that case to error-out (assert) instead.

(In reply to comment #1) > This is actually a problem with "hasSlicing": It is currently being tightened > so that the result of a slice operation *must* be convertible back to the > original type. If this is not the case, then the range will not be considered > sliceable. > > Once this is deployed, you will (should) be forwarded to the "correct" overload > of sortImpl: The one that doesn't use slicing. > > Still, could you please provide the code example that fails? This will help us > figure out which of the following is the culprit: > * The range? > * The definition of hasSlicing? > * The implementation of sort? > And correctly address the issue. OK: According to the new tests, the new definition of has slicing partially fixes the problem. However, there are currently no restraints for "sort", so the compilation error is: /usr/local/include/dmd2git/std/algorithm.d(7357): Error: template instance SortedRange!(Deque, "a < b") SortedRange!(Deque, "a < b") does not match template declaration SortedRange(Range, alias pred = "a < b") if (isRandomAccessRange!(Range) && hasLength!(Range)) I'll add a new restraint then.

That sounds very good. Thank you! p.s. Can you point me to the new slicing definition? Anyway thanks again

(In reply to comment #7) > That sounds very good. Thank you! > > p.s. Can you point me to the new slicing definition? Anyway thanks again The new slicing definition is only documented in code right now, but you'll find it here: https://github.com/D-Programming-Language/phobos/blob/2bbb33df2fa9f87ae73de6924031e1a854756ea1/std/range.d#L1236 To sum it up in a jiffy, the type returned by slice must be an exact type match of the original.* There are also special conditions in regards to infinite ranges and opDollar, but I'll let you read about those. *Not yet fully enforced due to a bug, but documented that way anyways, and will end up that way.

Closing as duplicate of 8368, which is currently being fixed. *** This issue has been marked as a duplicate of issue 8368 ***