diff options
author | Jure Ham <jure.ham@zemanta.com> | 2016-02-23 11:41:27 +0100 |
---|---|---|
committer | Ian Lance Taylor <iant@golang.org> | 2016-02-24 15:30:45 +0000 |
commit | 38d4511b104ad61d949d91652985bcdef8cbea5a (patch) | |
tree | 0b1f6c6cb7953453ae219a249cf3d560d987ac23 /src/sort | |
parent | 50c38d46e870435c17ac86957e2eb469ce41dd6d (diff) | |
download | go-38d4511b104ad61d949d91652985bcdef8cbea5a.tar.gz go-38d4511b104ad61d949d91652985bcdef8cbea5a.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>
Diffstat (limited to 'src/sort')
-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 5eb45c6d4a..ce3dc06f88 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++ { |