www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 9071] New: sort function won't compile but Range fits describtion

reply d-bugmail puremagic.com writes:
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: -------
Nov 24 2012
next sibling parent d-bugmail puremagic.com writes:
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: -------
Nov 25 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Nov 25 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Nov 25 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Nov 25 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Nov 25 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Dec 27 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Dec 27 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Dec 28 2012
prev sibling parent d-bugmail puremagic.com writes:
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: -------
Jan 02 2013