Skip to content

sort: clarify Slice comparator requirements #73420

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
jagprog5 opened this issue Apr 17, 2025 · 6 comments · May be fixed by #73421
Open

sort: clarify Slice comparator requirements #73420

jagprog5 opened this issue Apr 17, 2025 · 6 comments · May be fixed by #73421
Labels
Documentation Issues describing a change to documentation. NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made.
Milestone
Backlog

Comments

@jagprog5
Copy link

jagprog5 commented Apr 17, 2025 •
edited
Loading

The doc for sort.Slice states:

// The less function must satisfy the same requirements as
// the Interface type's Less method.

This is referring to the less function interface here:

// Less must describe a transitive ordering:
//  - if both Less(i, j) and Less(j, k) are true, then Less(i, k) must be true as well.
//  - if both Less(i, j) and Less(j, k) are false, then Less(i, k) must be false as well.

This describes only transitive ordering. In contrast, the underlying algorithm, pdqsort, requires strict weak ordering.

This is an important distinction. If a comparator is, for example:

  • reflexive
  • transitive

Then it will be conforming to the documented requirements yet will still cause crashes under nebulous implementation defined circumstances. e.g. the number of elements to sort is greater than 33, and elements happen to be in a specific order.

To fix:

Change the documented requirement of sort.Slice to what is stated in sort.SortFunc.

// SortFunc sorts the slice x in ascending order as determined by the cmp
// function. This sort is not guaranteed to be stable.
// cmp(a, b) should return a negative number when a < b, a positive number when
// a > b and zero when a == b or a and b are incomparable in the sense of
// a strict weak ordering.
//
// SortFunc requires that cmp is a strict weak ordering.
// See https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings.
// The function should return 0 for incomparable items.
@jagprog5 jagprog5 linked a pull request Apr 17, 2025 that will close this issue
Open
@gabyhelp
Copy link

Related Issues

Related Code Changes

(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)

@gabyhelp gabyhelp added the Documentation Issues describing a change to documentation. label Apr 17, 2025
@gopherbot
Copy link
Contributor

Change https://go.dev/cl/666355 mentions this issue: sort/slice: fix doc for sort.Slice

@randall77
Copy link
Contributor

I'm not certain that changing the spec is the way forward here. I'd rather change the implementation so that it conforms to the spec as written.
What is the case that causes a problem here? Is it when less(x,x) returns true? Can we detect that somehow in pdqsort and handle it, or maybe even bail out to a slower sort?

@jagprog5
Copy link
Author

jagprog5 commented Apr 17, 2025 •
edited
Loading

@randall77 think of this as a clarification and not a change to the doc. the doc is written poorly. practically speaking, everyone assumed strict weak ordering. but it was written in a way that, I'd argue, gave weaker requirements than is necessary.

I've changed the title

@jagprog5 jagprog5 changed the title incorrect doc sort.Slice comparator clarify doc sort.Slice comparator Apr 17, 2025
@randall77
Copy link
Contributor

Should we just require a strict weak ordering everywhere then?
(I'm not sure why in the CL sort.Slice and sort.SliceStable have explicitly different requirements.)

@jagprog5
Copy link
Author

jagprog5 commented Apr 17, 2025 •
edited
Loading

Should we just require a strict weak ordering everywhere then?

Yes, I've changed it. we already require a strict weak ordering everywhere, this just clarifies that.

As for the difference in sort vs stable, I've dropped that. There is a different in the requirements only from the implementation, but not the doc. I'd prefer it to be part of the doc / spec as well, but that would require more work in justifying. And, I see that C++ stdlib doesn't provide a public distinction either, so it's probably best to just stay consistent anyway.

@seankhliao seankhliao changed the title clarify doc sort.Slice comparator sort: clarify Slice comparator requirements Apr 17, 2025
@prattmic prattmic added the NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made. label Apr 18, 2025
@prattmic prattmic added this to the Backlog milestone Apr 18, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
Documentation Issues describing a change to documentation. NeedsDecision Feedback is required from experts, contributors, and/or the community before a change can be made.
Projects
None yet
Milestone
Backlog
Development

Successfully merging a pull request may close this issue.

sort: clarify Less doc jagprog5/go
5 participants
@prattmic @randall77 @gopherbot @jagprog5 @gabyhelp