<< Back to previous view

[CLJS-204] Bug in sort Created: 25/Apr/12  Updated: 27/Jul/13  Resolved: 18/May/12

Status: Closed
Project: ClojureScript
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Critical
Reporter: Sean Nilan Assignee: Hubert Iwaniuk
Resolution: Completed Votes: 0
Labels: clojure
Environment:

Mac OS X, recently cloned ClojureScript repository


Attachments: Text File CLJS-204-IComparable.patch    
Patch: Code and Test

 Description   

The sort function (and thus sort-by) do not seem to be behaving as they would in normal Clojure. For example, in my ClojureScript REPL I have:

ClojureScript:cljs.user> (def values (list [-11 10] [-8 12] [-15 -4] [4 5]))
([-11 10] [-8 12] [-15 -4] [4 5])
ClojureScript:cljs.user> (sort values)
([-11 10] [-15 -4] [-8 12] [4 5])

But in the Clojure REPL, you get what one would expect:
user=> (def values (list [-11 10] [-8 12] [-15 -4] [4 5]))
#'setback.core/values
user=> (sort values)
([-15 -4] [-11 10] [-8 12] [4 5])

I have only noticed this bug for sorting vectors, since in Clojure vectors are sorted position by position.



 Comments   
Comment by Sean Nilan [ 25/Apr/12 8:52 AM ]

The bug is actually in the compare function, which uses the google.array.defaultCompare as the compare function for vectors. A simple patch such as below could fix the problem:

(defn vector-compare
[v1 v2]
(cond
(and (empty? v1) (empty? v2))
0
(empty? v1)
-1
(empty? v2)
1
:default
(let [cmp (apply compare (map first [v1 v2]))]
(if (zero? cmp)
(vector-compare (rest v1) (rest v2))
cmp))))

(defn compare
"Comparator. Returns a negative number, zero, or a positive number
when x is logically 'less than', 'equal to', or 'greater than'
y. Uses google.array.defaultCompare for objects of the same type
and special-cases nil to be less than any other object."
[x y]
(cond
(and (vector? x) (vector? y)) (vector-compare x y)
(identical? (type x) (type y)) (garray/defaultCompare x y)
(nil? x) -1
(nil? y) 1
:else (throw (js/Error. "compare on non-nil objects of different types"))))

Comment by David Nolen [ 25/Apr/12 8:54 AM ]

Thanks. We need a IComparable protocol.

Comment by Hubert Iwaniuk [ 16/May/12 3:11 AM ]

IComparable protocol, implementations and tests.

Comment by David Nolen [ 16/May/12 8:15 AM ]

Can we squash the commits here? Thanks!

Comment by Hubert Iwaniuk [ 16/May/12 8:30 AM ]

Commits squashed.

Comment by David Nolen [ 16/May/12 11:31 AM ]

Why do we need to extend IComparable to strings, arrays, boolean, and number?

Comment by Hubert Iwaniuk [ 17/May/12 2:17 PM ]

booleans - are supported in clj
number - special case in clj, not sure if it brings any speed increase, will test with jsperf
arrays - are supported in clj
strings - to support symbols and keywords

Comment by Hubert Iwaniuk [ 18/May/12 7:46 AM ]

Simplified version, just to solve comparing vectors.

Comment by David Nolen [ 18/May/12 7:28 PM ]

fixed, http://github.com/clojure/clojurescript/commit/43ff1c4adea322e6edc1d368ff128f2ad47406a5

Generated at Wed Apr 23 08:57:38 CDT 2014 using JIRA 4.4#649-r158309.