View mode: basic / threaded / horizontal-split · Log in · Help
November 24, 2012
[Issue 9071] New: sort function won't compile but Range fits describtion
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
[Issue 9071] sort function won't compile but Range fits describtion
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
[Issue 9071] sort function won't compile but Range fits describtion
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
[Issue 9071] sort function won't compile but Range fits describtion
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
[Issue 9071] sort function won't compile but Range fits describtion
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
[Issue 9071] sort function won't compile but Range fits describtion
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
[Issue 9071] sort function won't compile but Range fits describtion
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
[Issue 9071] sort function won't compile but Range fits describtion
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
[Issue 9071] sort function won't compile but Range fits describtion
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
[Issue 9071] sort function won't compile but Range fits describtion
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