www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 8469] New: isSorted fails with predicate "a.length < b.length ? true : a < b"

reply d-bugmail puremagic.com writes:
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: -------
Jul 29 2012
next sibling parent d-bugmail puremagic.com writes:
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: -------
Jul 30 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Jul 30 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Jul 30 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Jul 30 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Jul 30 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Jul 30 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Jul 30 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Jul 30 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Jul 31 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8469



--- Comment #10 from github-bugzilla puremagic.com 2012-08-04 18:47:12 PDT ---
Commit pushed to master at https://github.com/D-Programming-Language/phobos

https://github.com/D-Programming-Language/phobos/commit/fc99e5583e16897b487a60188421967f664ced02
Merge pull request #729 from andralex/bug8469

Added additional check to isSorted to detect invalid predicates

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 04 2012
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8469


Jonathan M Davis <jmdavisProg gmx.com> changed:

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


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