November 24, 2012
http://d.puremagic.com/issues/show_bug.cgi?id=9071

           Summary: sort function won't compile but Range fits describtion
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody@puremagic.com
        ReportedBy: rburners@gmail.com


--- Comment #0 from Robert Schadek <rburners@gmail.com> 2012-11-24 06:32:03 PST ---
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));

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
November 25, 2012
http://d.puremagic.com/issues/show_bug.cgi?id=9071


monarchdodra@gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |monarchdodra@gmail.com


--- Comment #1 from monarchdodra@gmail.com 2012-11-25 03:15:54 PST ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
November 25, 2012
http://d.puremagic.com/issues/show_bug.cgi?id=9071



--- Comment #2 from Robert Schadek <rburners@gmail.com> 2012-11-25 04:53:18 PST ---
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

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
November 25, 2012
http://d.puremagic.com/issues/show_bug.cgi?id=9071


monarchdodra@gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|nobody@puremagic.com        |monarchdodra@gmail.com
           Severity|enhancement                 |normal


--- Comment #3 from monarchdodra@gmail.com 2012-11-25 05:12:32 PST ---
(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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
November 25, 2012
http://d.puremagic.com/issues/show_bug.cgi?id=9071



--- Comment #4 from Robert Schadek <rburners@gmail.com> 2012-11-25 05:54:40 PST ---
http://dpaste.dzfl.pl/163a9600

prints the exact same error

thanks

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
November 25, 2012
http://d.puremagic.com/issues/show_bug.cgi?id=9071



--- Comment #5 from monarchdodra@gmail.com 2012-11-25 07:30:14 PST ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
December 27, 2012
http://d.puremagic.com/issues/show_bug.cgi?id=9071



--- Comment #6 from monarchdodra@gmail.com 2012-12-27 06:00:26 PST ---
(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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
December 27, 2012
http://d.puremagic.com/issues/show_bug.cgi?id=9071



--- Comment #7 from Robert Schadek <rburners@gmail.com> 2012-12-27 14:04:53 PST ---
That sounds very good. Thank you!

p.s. Can you point me to the new slicing definition? Anyway thanks again

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
December 28, 2012
http://d.puremagic.com/issues/show_bug.cgi?id=9071



--- Comment #8 from monarchdodra@gmail.com 2012-12-28 01:30:02 PST ---
(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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
January 02, 2013
http://d.puremagic.com/issues/show_bug.cgi?id=9071


monarchdodra@gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |DUPLICATE


--- Comment #9 from monarchdodra@gmail.com 2013-01-02 06:53:16 PST ---
Closing as duplicate of 8368, which is currently being fixed.

*** This issue has been marked as a duplicate of issue 8368 ***

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Top | Discussion index | About this forum | D home