diff options
author | Jure Ham <jure.ham@zemanta.com> | 2016-02-23 11:41:27 +0100 |
---|---|---|
committer | Andrew Gerrand <adg@golang.org> | 2016-04-14 05:21:10 +0000 |
commit | e44998bcd25af29785354c8a5bcfb6348121f3b8 (patch) | |
tree | 684a31dbcdf593f0df1cb99050d827cb773d57a0 | |
parent | 002cf2820d49009e6e5590d53b8ee640bfd6eb5c (diff) | |
download | go-e44998bcd25af29785354c8a5bcfb6348121f3b8.tar.gz go-e44998bcd25af29785354c8a5bcfb6348121f3b8.zip |
sort: fix for nondeterministic less function in quicksort pivot
Fixes #14377
Change-Id: I130a6e1b8bc827db44efd0a74e759b894ecc4977
Reviewed-on: https://go-review.googlesource.com/19823
Reviewed-by: Ian Lance Taylor <iant@golang.org>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-on: https://go-review.googlesource.com/22039
-rw-r--r-- | src/sort/sort.go | 14 | ||||
-rw-r--r-- | src/sort/sort_test.go | 37 |
2 files changed, 44 insertions, 7 deletions
diff --git a/src/sort/sort.go b/src/sort/sort.go index ac8f4a661f..ee437d3faf 100644 --- a/src/sort/sort.go +++ b/src/sort/sort.go @@ -119,15 +119,15 @@ func doPivot(data Interface, lo, hi int) (midlo, midhi int) { pivot := lo a, c := lo+1, hi-1 - for ; a != c && data.Less(a, pivot); a++ { + for ; a < c && data.Less(a, pivot); a++ { } b := a for { - for ; b != c && !data.Less(pivot, b); b++ { // data[b] <= pivot + for ; b < c && !data.Less(pivot, b); b++ { // data[b] <= pivot } - for ; b != c && data.Less(pivot, c-1); c-- { // data[c-1] > pivot + for ; b < c && data.Less(pivot, c-1); c-- { // data[c-1] > pivot } - if b == c { + if b >= c { break } // data[b] > pivot; data[c-1] <= pivot @@ -167,11 +167,11 @@ func doPivot(data Interface, lo, hi int) (midlo, midhi int) { // data[a <= i < b] unexamined // data[b <= i < c] = pivot for { - for ; a != b && !data.Less(b-1, pivot); b-- { // data[b] == pivot + for ; a < b && !data.Less(b-1, pivot); b-- { // data[b] == pivot } - for ; a != b && data.Less(a, pivot); a++ { // data[a] < pivot + for ; a < b && data.Less(a, pivot); a++ { // data[a] < pivot } - if a == b { + if a >= b { break } // data[a] == pivot; data[b-1] < pivot diff --git a/src/sort/sort_test.go b/src/sort/sort_test.go index 6c36f30e0e..a5da6b2630 100644 --- a/src/sort/sort_test.go +++ b/src/sort/sort_test.go @@ -109,6 +109,43 @@ func TestReverseSortIntSlice(t *testing.T) { } } +type nonDeterministicTestingData struct { + r *rand.Rand +} + +func (t *nonDeterministicTestingData) Len() int { + return 500 +} +func (t *nonDeterministicTestingData) Less(i, j int) bool { + if i < 0 || j < 0 || i >= t.Len() || j >= t.Len() { + panic("nondeterministic comparison out of bounds") + } + return t.r.Float32() < 0.5 +} +func (t *nonDeterministicTestingData) Swap(i, j int) { + if i < 0 || j < 0 || i >= t.Len() || j >= t.Len() { + panic("nondeterministic comparison out of bounds") + } +} + +func TestNonDeterministicComparison(t *testing.T) { + // Ensure that sort.Sort does not panic when Less returns inconsistent results. + // See https://golang.org/issue/14377. + defer func() { + if r := recover(); r != nil { + t.Error(r) + } + }() + + td := &nonDeterministicTestingData{ + r: rand.New(rand.NewSource(0)), + } + + for i := 0; i < 10; i++ { + Sort(td) + } +} + func BenchmarkSortString1K(b *testing.B) { b.StopTimer() for i := 0; i < b.N; i++ { |