http://d.puremagic.com/issues/show_bug.cgi?id=8469

           Summary: isSorted fails with predicate "a.length < b.length ?
                    true : a < b"
           Product: D
           Version: unspecified
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody@puremagic.com
        ReportedBy: jmdavisProg@gmx.com


--- Comment #0 from Jonathan M Davis <jmdavisProg@gmx.com> 2012-07-29 19:44:44 PDT ---
This code fails the assertion:

import std.algorithm;
import std.stdio;

void main()
{
    string[] x = ["_10", "_20", "_100"];
    assert(isSorted!"a.length < b.length ? true : a < b"(x));
}

However, it _is_ sorted according to the predicate, so the assertion should pass.

I ran into this because sort throws an AssertError sorting ["_100", "_10", "_20"] using that predicate, claiming that the sorting failed, when it actually succeeded. So, not only is this messing up isSorted, but it messes up sort in non-release mode.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=8469


Andrei Alexandrescu <andrei@metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |andrei@metalanguage.com


--- Comment #1 from Andrei Alexandrescu <andrei@metalanguage.com> 2012-07-30 06:48:57 PDT ---
That's quite a pickle. The predicate is not a valid sorting relation because according to it both "_20" < "_100" and "_100" < "_20" are true (so it's not antisymmetric). That's how isSorted operates - it compares adjacent elements with the predicate in swapped order.

We could make isSorted work with broken predicates (at a performance cost for everyone), but then people may think if that works sort should works too with such predicates etc. etc.

Best we can is include an assert in isSorted that catches bad predicates in debug builds. Thoughts?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=8469


bearophile_hugs@eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_hugs@eml.cc


--- Comment #2 from bearophile_hugs@eml.cc 2012-07-30 07:18:29 PDT ---
(In reply to comment #1)
> That's quite a pickle. The predicate is not a valid sorting relation because according to it both "_20" < "_100" and "_100" < "_20" are true (so it's not antisymmetric). That's how isSorted operates - it compares adjacent elements with the predicate in swapped order.
> 
> We could make isSorted work with broken predicates (at a performance cost for everyone), but then people may think if that works sort should works too with such predicates etc. etc.
> 
> Best we can is include an assert in isSorted that catches bad predicates in debug builds. Thoughts?

Maybe some more advanced languages are or will be able to catch part of the mistakes in the sorting relation at compile-time.

I suggest to leave sort()/isSorted() as they are, and add an explanation in the
docs of sort() and isSorted() functions that explains the basics of this
situation, what's a bad and good sorting relation.

Generally when the compiler can't catch something at compile-time, the invariants should be written down in the documentation for the programmer.

One characteristic of the the history programming languages is a progressive increase of expressivity, that allows to move move more and more information from the comments written for the programmer to invariants and code that the compiler is able to understand, verify and use.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=8469



--- Comment #3 from Andrei Alexandrescu <andrei@metalanguage.com> 2012-07-30 07:28:01 PDT ---
What did I just read?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=8469



--- Comment #4 from bearophile_hugs@eml.cc 2012-07-30 08:09:53 PDT ---
(In reply to comment #3)
> What did I just read?

An insightful answer and a solution to your problem :-)

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=8469



--- Comment #5 from Jonathan M Davis <jmdavisProg@gmx.com> 2012-07-30 10:26:10 PDT ---
Hmmm. I didn't realize that the predicate was screwed up, but it does indeed look like it was badly written (I didn't even think about comparing in both directions like that - I should have). I guess that I was in too much of a hurry when I wrote it.

Well, sort gives an assertion failure which is pretty bad in this situation in that it claims that the sorting didn't work, which looks completely wrong, since it _did_ work.

I definitely think that it makes the most sense to make isSorted assert on bad predicates and have it clearly state that predicate was bad because it's antisymmetric. Then it's clear that the problem is with the predicate and not sorted or isSorted.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=8469



--- Comment #6 from bearophile_hugs@eml.cc 2012-07-30 10:37:10 PDT ---
(In reply to comment #5)

> I definitely think that it makes the most sense to make isSorted assert on bad predicates and have it clearly state that predicate was bad because it's antisymmetric.

How do you do this?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=8469



--- Comment #7 from Jonathan M Davis <jmdavisProg@gmx.com> 2012-07-30 10:39:15 PDT ---
> How do you do this?

I don't know, but from Andrei's comment, he seems to think that it's possible.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=8469



--- Comment #8 from Andrei Alexandrescu <andrei@metalanguage.com> 2012-07-30 10:47:16 PDT ---
It's very simple, if isSorted finds two adjacent elements a, b that satisfy
pred(b, a) it can also check whether pred(a, b) and assert if that's also true.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=8469



--- Comment #9 from bearophile_hugs@eml.cc 2012-07-31 02:01:53 PDT ---
(In reply to comment #8)
> It's very simple, if isSorted finds two adjacent elements a, b that satisfy
> pred(b, a) it can also check whether pred(a, b) and assert if that's also true.

I see, with run-time tests.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------