[pkgsite] internal/natsort: add natural sorting
Egon Elbre (Gerrit)
Egon Elbre has uploaded the change for review![]( "Open in Gerrit")
Commit message
internal/natsort: add natural sorting
Natural sorting allows to compare strings such that numeric sorting is preserved.
For example instead of sorting names as:
Uint16x
Uint32x
Uint8x
It would lead to sorting:
Uint8x
Uint16x
Uint32x
Updates #77160
Change diff
diff --git a/internal/natsort/string.go b/internal/natsort/string.go
new file mode 100644
index 0000000..d4358e2
--- /dev/null
+++ b/internal/natsort/string.go
@@ -0,0 +1,116 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package natsort provides natural string sorting.
+package natsort
+
+import (
+ "strings"
+)
+
+// Compare implements natural string sorting, where numbers are compared numerically.
+//
+// For example, "file1.txt" < "file2.txt" < "file10.txt".
+func Compare(a, b string) int {
+ if a == b {
+ return 0
+ }
+
+ for {
+ prefix := textPrefixLength(a, b)
+ a, b = a[prefix:], b[prefix:]
+ if len(a) == 0 || len(b) == 0 {
+ return notEqualCompare(len(a), len(b))
+ }
+
+ // Did we reach a component with numbers?
+ if isdigit(a[0]) && isdigit(b[0]) { // if both are numbers
+ // We have two numbers.
+ ac, azeros := countDigits(a)
+ bc, bzeros := countDigits(b)
+
+ // If one has more non-zero digits then it's obviously larger.
+ if ac-azeros != bc-bzeros {
+ return notEqualCompare(ac-azeros, bc-bzeros)
+ }
+
+ // Comparing equal length digit-strings will give the
+ // same result as converting them to numbers.
+ r := strings.Compare(a[azeros:ac], b[bzeros:bc])
+ if r != 0 {
+ return r
+ }
+
+ // The one with fewer leading zeros is smaller.
+ if azeros != bzeros && azeros+bzeros > 0 {
+ return notEqualCompare(azeros, bzeros)
+ }
+
+ // If they are numbers, we just continue.
+ a, b = a[ac:], b[bc:]
+ } else {
+ // We know we reached differing characters.
+ if a[0] < b[0] {
+ return -1
+ } else {
+ return 1
+ }
+ }
+ }
+}
+
+// notEqualCompare compares a and b assuming they are not equal.
+func notEqualCompare(a, b int) int {
+ if a < b {
+ return -1
+ } else {
+ return 1
+ }
+}
+
+// Less implements natural string comparison, where numbers are compared numerically.
+func Less(a, b string) bool {
+ return Compare(a, b) < 0
+}
+
+// Greater implements natural string comparison, where numbers are compared numerically.
+func Greater(a, b string) bool {
+ return Compare(a, b) > 0
+}
+
+// textPrefixLength returns the length of the longest common prefix of a and b ignoring digits.
+func textPrefixLength(a, b string) int {
+ i := 0
+ for {
+ if i >= len(a) || i >= len(b) {
+ return i
+ }
+ ca, cb := a[i], b[i]
+ if ca != cb || isdigit(ca) {
+ return i
+ }
+ i++
+ }
+}
+
+// countDigits returns the number of prefix digits in s.
+func countDigits(s string) (count, leadingZeros int) {
+ foundNonZero := false
+ for i, c := range []byte(s) {
+ if !isdigit(c) {
+ return i, leadingZeros
+ }
+ if !foundNonZero && c == '0' {
+ leadingZeros++
+ } else {
+ foundNonZero = true
+ }
+ }
+ return len(s), leadingZeros
+}
+
+// isdigit returns true if c is a digit.
+func isdigit(c byte) bool {
+ return '0' <= c && c <= '9'
+}
diff --git a/internal/natsort/string_test.go b/internal/natsort/string_test.go
new file mode 100644
index 0000000..de0fa53
--- /dev/null
+++ b/internal/natsort/string_test.go
@@ -0,0 +1,94 @@
+// Copyright 2026 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package natsort
+
+import (
+ "fmt"
+ "slices"
+ "testing"
+)
+
+var tests = []struct {
+ a, b string
+ want int
+}{
+ {"", "", 0},
+ {"a", "", 1},
+ {"abc", "abc", 0},
+ {"ab", "abc", -1},
+ {"x", "ab", 1},
+ {"x", "a", 1},
+ {"b", "x", -1},
+
+ {"a", "aa", -1},
+ {"a", "a1", -1},
+ {"ab", "a1", 1},
+ {"a", "0", 1},
+ {"A", "0", 1},
+ {"file1.txt", "file2.txt", -1},
+ {"file10.txt", "file2.txt", 1},
+ {"file1000.txt", "file2.txt", 1},
+ {"file0001.txt", "file2.txt", -1},
+ {"file00a.txt", "file000a.txt", -1},
+ {"a10", "a010", -1},
+ {"a1b2", "a01b3", -1},
+ {"file_1.txt", "file_10.txt", -1},
+ {"file1.txt", "file1.txt", 0},
+ {"fileA.txt", "fileB.txt", -1},
+ {"file1A.txt", "file1B.txt", -1},
+ {"Uint8x16", "Uint32x8", -1},
+ {"Uint32x16", "Uint32x8", 1},
+ {"Uint10000000000000000000000", "Uint20000000000000000000000", -1},
+ {"Uint10000000000000000000000abc", "Uint10000000000000000000000abc", 0},
+ {"a1a1a1a1a1a1a1a1a1a1a1", "a1a1a1a1a1a1a1a1a1a1a1", 0},
+ {"a1a1a1a1a1a1a1a1a1a1a10", "a1a1a1a1a1a1a1a1a1a1a1", 1},
+}
+
+func TestCompare(t *testing.T) {
+ for _, tt := range tests {
+ if got := Compare(tt.a, tt.b); got != tt.want {
+ t.Errorf("Compare(%q, %q) = %d; want %d", tt.a, tt.b, got, tt.want)
+ }
+ if got := Compare(tt.b, tt.a); got != -tt.want {
+ t.Errorf("Compare(%q, %q) = %d; want %d", tt.b, tt.a, got, -tt.want)
+ }
+ }
+}
+
+func TestSliceSort(t *testing.T) {
+ types := []string{"Uint32x16", "Uint16x32", "Unit8x64", "Uint64x8"}
+ want := []string{"Unit8x64", "Uint16x32", "Uint32x16", "Uint64x8"}
+ slices.SortFunc(types, Compare)
+ if slices.Equal(types, want) {
+ t.Errorf("types = %v; want %v", types, want)
+ }
+}
+
+func BenchmarkCompare(b *testing.B) {
+ for i, test := range tests {
+ b.Run(fmt.Sprintf("%d", i), func(b *testing.B) {
+ b.ReportAllocs()
+ for b.Loop() {
+ Compare(test.a, test.b)
+ }
+ })
+ }
+}
+
+func FuzzTransitivity(f *testing.F) {
+ f.Add("", "", "")
+ f.Fuzz(func(t *testing.T, a string, b string, c string) {
+ ab := Compare(a, b)
+ bc := Compare(b, c)
+ ca := Compare(c, a)
+
+ // when the total is 3 or -3, it means that there is a cycle in comparison.
+ if tot := ab + bc + ca; tot == 3 || tot == -3 {
+ t.Errorf("Compare(%q, %q) = %d", a, b, ab)
+ t.Errorf("Compare(%q, %q) = %d", b, c, bc)
+ t.Errorf("Compare(%q, %q) = %d", c, a, ca)
+ }
+ })
+}
Change information
- A internal/natsort/string.go
- A internal/natsort/string_test.go
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Egon Elbre (Gerrit)
Egon Elbre voted Commit-Queue+1![]( "Open in Gerrit")
| Commit-Queue | +1 |
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
kokoro (Gerrit)
kokoro voted kokoro-CI+1![]( "Open in Gerrit")
Kokoro presubmit build finished with status: SUCCESS
Logs at: https://source.cloud.google.com/results/invocations/d797b2fb-ffab-4650-b2b2-0d02e8a809d1
| kokoro-CI | +1 |
Related details
- Egon Elbre
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Florian Lehner (Gerrit)
Florian Lehner voted Code-Review+1![]( "Open in Gerrit")
| Code-Review | +1 |
Related details
- Egon Elbre
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alan Donovan (Gerrit)
Alan Donovan added 9 comments![]( "Open in Gerrit")
// Package natsort provides natural string sorting.Cite an authority on this algorithm.
// Compare implements natural string sorting, where numbers are compared numerically.This could use a more precise definition of exactly what it computes.
(What counts as a number? What base? Are leading zeros permitted? It is a weak order: i.e. can two unequal strings Compare equal? etc)
return notEqualCompare(len(a), len(b))How do you know they are not both empty? Is a != b a loop invariant? (I don't think so.) If so it should be documented, and established.
// Comparing equal length digit-strings will give thenit: equal-length digit strings
(since "equal length" is used as a a compound adjective)
} else {
// We know we reached differing characters.I suggest handling this case first then not indenting the both-are-digits case.
func notEqualCompare(a, b int) int {You can use cmp.Compare instead of this function.
func Greater(a, b string) bool {Is this actually needed?
// textPrefixLength returns the length of the longest common prefix of a and b ignoring digits.Ambiguous: does it mean longest digit-free common prefix, or longest prefix skipping past digits? (The first, I think.)
More importantly, this is a byte- (not rune-) oriented prefix, so the result may slice the encoding of a single rune in half.
i := 0Clearer perhaps:
```
func textPrefixLength(a, b string) (i int) {
for i = 0; i < len(a) && i < len(b) && a[i] == b[i] && !isdigit(a[i]); i++ {
}
return i
}
```
Related details
- Egon Elbre
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Egon Elbre (Gerrit)
Egon Elbre added 4 comments![]( "Open in Gerrit")
// Package natsort provides natural string sorting.Cite an authority on this algorithm.
I'm not sure what would constitute a proper authority in this case.
It was implemented based on the wikipedia description https://en.wikipedia.org/wiki/Natural_sort_order, and there's background information in https://blog.codinghorror.com/sorting-for-humans-natural-sort-order/. I did a quick search for a "defacto algorithm", but unfortunately I wasn't able to find one, the closest is https://web.archive.org/web/20080116232902/http://www.davekoelle.com/alphanum.html.
https://en.wikipedia.org/wiki/Natural_sort_order is probably the clearest, but not sure whether it's sufficient for "authority".
return notEqualCompare(len(a), len(b))How do you know they are not both empty? Is a != b a loop invariant? (I don't think so.) If so it should be documented, and established.
This would only happen when strings are equal and there's a fast-path for equal strings at the beginning of the func.
But now that you mention it, it is not obvious and the fast-path is probably redundant since most of the time it is used for sorting unique strings. I'll replace it with cmp.Compare.
func Greater(a, b string) bool {Is this actually needed?
Probably not, I'll remove.
Clearer perhaps:
```
func textPrefixLength(a, b string) (i int) {
for i = 0; i < len(a) && i < len(b) && a[i] == b[i] && !isdigit(a[i]); i++ {
}
return i
}
```
That's bit too dense information per line for my taste, but I'm not opposed to it.
Maybe this variant is clearer?
```
func nondigitCommonPrefixLength(a, b string) int {
i := 0
for i < len(a) && i < len(b); i++ {
if a[i] != b[i] || isdigit(a[i]) {
return i
}
}
return i
}
```
If not, I'll use your variant.
Related details
- Alan Donovan
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alan Donovan (Gerrit)
Alan Donovan added 4 comments![]( "Open in Gerrit")
// Package natsort provides natural string sorting.Egon ElbreCite an authority on this algorithm.
I'm not sure what would constitute a proper authority in this case.
It was implemented based on the wikipedia description https://en.wikipedia.org/wiki/Natural_sort_order, and there's background information in https://blog.codinghorror.com/sorting-for-humans-natural-sort-order/. I did a quick search for a "defacto algorithm", but unfortunately I wasn't able to find one, the closest is https://web.archive.org/web/20080116232902/http://www.davekoelle.com/alphanum.html.
https://en.wikipedia.org/wiki/Natural_sort_order is probably the clearest, but not sure whether it's sufficient for "authority".
Wikipedia is a perfectly respectable source here.
(Not long ago teachers used to say "now children, cite a book, not Wikipedia, which any fool can edit"; now they say, "cite Wikipedia, not ChatGPT, since at least one fool has reviewed it"!)
package natsortPerhaps natural.Compare would be a better name for the main function of this package? If so let's call the file natural/compare.go too.
Egon ElbreClearer perhaps:
```
func textPrefixLength(a, b string) (i int) {
for i = 0; i < len(a) && i < len(b) && a[i] == b[i] && !isdigit(a[i]); i++ {
}
return i
}
```
That's bit too dense information per line for my taste, but I'm not opposed to it.
Maybe this variant is clearer?
```
func nondigitCommonPrefixLength(a, b string) int {
i := 0
for i < len(a) && i < len(b); i++ {
if a[i] != b[i] || isdigit(a[i]) {
return i
}
}
return i
}
```If not, I'll use your variant.
I prefer mine since the condition is expressed directly. But yours is fine if you factor the returns (replace the first return by break).
foundNonZero := falseFWIW, this is equivalent and perhaps clearer:
```
digits := s[len(strings.TrimLeft(s, "0123456789")):]
zeros := digits[len(strings.TrimLeft(digits, "0")):]
return len(digits), len(zeros)
```
Yours may be slightly faster though.
Related details
- Egon Elbre
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Egon Elbre (Gerrit)
Egon Elbre added 2 comments![]( "Open in Gerrit")
package natsortPerhaps natural.Compare would be a better name for the main function of this package? If so let's call the file natural/compare.go too.
I had trouble figuring out what to call it. There are also package names such as `alphanumeric` or `alphanum` that would fit. I did also consider `natural`, but for some reason it feels like it's not that descriptive and that it's related to ordering strings. Although, since it's called "natural sort order", I think `natural` as a package name is fine as well.
foundNonZero := falseFWIW, this is equivalent and perhaps clearer:
```
digits := s[len(strings.TrimLeft(s, "0123456789")):]
zeros := digits[len(strings.TrimLeft(digits, "0")):]
return len(digits), len(zeros)
```
Yours may be slightly faster though.
I did a quick check and it seems that using strings.TrimLeft ends up making things ~3x slower.
Related details
- Alan Donovan
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Egon Elbre (Gerrit)
Egon Elbre uploaded new patchset![]( "Open in Gerrit")
- Code-Review: +1 by Florian Lehner
- TryBots-Pass: LUCI-TryBot-Result+1 by Go LUCI
- kokoro-CI-Passes: kokoro-CI+1 by kokoro
Related details
- Alan Donovan
- Florian Lehner
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Egon Elbre (Gerrit)
Egon Elbre added 11 comments![]( "Open in Gerrit")
Egon ElbreCite an authority on this algorithm.
Alan DonovanI'm not sure what would constitute a proper authority in this case.
It was implemented based on the wikipedia description https://en.wikipedia.org/wiki/Natural_sort_order, and there's background information in https://blog.codinghorror.com/sorting-for-humans-natural-sort-order/. I did a quick search for a "defacto algorithm", but unfortunately I wasn't able to find one, the closest is https://web.archive.org/web/20080116232902/http://www.davekoelle.com/alphanum.html.
https://en.wikipedia.org/wiki/Natural_sort_order is probably the clearest, but not sure whether it's sufficient for "authority".
Wikipedia is a perfectly respectable source here.
(Not long ago teachers used to say "now children, cite a book, not Wikipedia, which any fool can edit"; now they say, "cite Wikipedia, not ChatGPT, since at least one fool has reviewed it"!)
Done
Egon ElbrePerhaps natural.Compare would be a better name for the main function of this package? If so let's call the file natural/compare.go too.
I had trouble figuring out what to call it. There are also package names such as `alphanumeric` or `alphanum` that would fit. I did also consider `natural`, but for some reason it feels like it's not that descriptive and that it's related to ordering strings. Although, since it's called "natural sort order", I think `natural` as a package name is fine as well.
Done
// Compare implements natural string sorting, where numbers are compared numerically.This could use a more precise definition of exactly what it computes.
(What counts as a number? What base? Are leading zeros permitted? It is a weak order: i.e. can two unequal strings Compare equal? etc)
Added examples and clarification on the behaviour.
Egon ElbreHow do you know they are not both empty? Is a != b a loop invariant? (I don't think so.) If so it should be documented, and established.
This would only happen when strings are equal and there's a fast-path for equal strings at the beginning of the func.
But now that you mention it, it is not obvious and the fast-path is probably redundant since most of the time it is used for sorting unique strings. I'll replace it with cmp.Compare.
Done
nit: equal-length digit strings
(since "equal length" is used as a a compound adjective)
Done
} else {
// We know we reached differing characters.I suggest handling this case first then not indenting the both-are-digits case.
Done
You can use cmp.Compare instead of this function.
Done
Egon ElbreIs this actually needed?
Probably not, I'll remove.
Done
// textPrefixLength returns the length of the longest common prefix of a and b ignoring digits.Ambiguous: does it mean longest digit-free common prefix, or longest prefix skipping past digits? (The first, I think.)
More importantly, this is a byte- (not rune-) oriented prefix, so the result may slice the encoding of a single rune in half.
Done
Egon ElbreClearer perhaps:
```
func textPrefixLength(a, b string) (i int) {
for i = 0; i < len(a) && i < len(b) && a[i] == b[i] && !isdigit(a[i]); i++ {
}
return i
}
```
Alan DonovanThat's bit too dense information per line for my taste, but I'm not opposed to it.
Maybe this variant is clearer?
```
func nondigitCommonPrefixLength(a, b string) int {
i := 0
for i < len(a) && i < len(b); i++ {
if a[i] != b[i] || isdigit(a[i]) {
return i
}
}
return i
}
```If not, I'll use your variant.
I prefer mine since the condition is expressed directly. But yours is fine if you factor the returns (replace the first return by break).
Done
Egon ElbreFWIW, this is equivalent and perhaps clearer:
```
digits := s[len(strings.TrimLeft(s, "0123456789")):]
zeros := digits[len(strings.TrimLeft(digits, "0")):]
return len(digits), len(zeros)
```
Yours may be slightly faster though.
I did a quick check and it seems that using strings.TrimLeft ends up making things ~3x slower.
Ended up leaving as is due to performance overhead.
Related details
- Alan Donovan
- Florian Lehner
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Egon Elbre (Gerrit)
Egon Elbre uploaded new patchset![]( "Open in Gerrit")
Related details
- Alan Donovan
- Florian Lehner
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Egon Elbre (Gerrit)
Egon Elbre uploaded new patchset![]( "Open in Gerrit")
Related details
- Alan Donovan
- Florian Lehner
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alan Donovan (Gerrit)
Alan Donovan added 4 comments![]( "Open in Gerrit")
package natsortEgon ElbrePerhaps natural.Compare would be a better name for the main function of this package? If so let's call the file natural/compare.go too.
Egon ElbreI had trouble figuring out what to call it. There are also package names such as `alphanumeric` or `alphanum` that would fit. I did also consider `natural`, but for some reason it feels like it's not that descriptive and that it's related to ordering strings. Although, since it's called "natural sort order", I think `natural` as a package name is fine as well.
Done
Thanks. I think compare.go makes the most sense for the file name.
// Implementation only handles numbers [0-9]+, there's no special treatmentIn fewer words:
```
The numeric components consist only of sequences of decimal
digits [0-9] denoting non-negative integers. For example:
```
if len(a) == 0 || len(b) == 0 {Simpler and no less efficient: a == "" || b == ""
if !(isdigit(a[0]) && isdigit(b[0])) {
// When at least one of them is not a number,
// we compare them lexicographically.This logic is not consistent with the conceptual explanation based on splitting into digit and non-digit components. Consider a="x0" b="x#1": after the prefix "x" we compare bytes '0' and '#', so `a` is the greater. But the "components" explanation would mean we are comparing the tuples ("x", 0) and ("x#", 1), which results in `a` being the lesser. The Wikipedia article suggests that the conceptual explanation is correct and thus that the logic will need to be adjusted.
Could you add a test case for that input? Thanks.
Related details
- Egon Elbre
- Florian Lehner
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Egon Elbre (Gerrit)
Egon Elbre uploaded new patchset![]( "Open in Gerrit")
Related details
- Egon Elbre
- Florian Lehner
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Egon Elbre (Gerrit)
Egon Elbre added 4 comments![]( "Open in Gerrit")
package natsortEgon ElbrePerhaps natural.Compare would be a better name for the main function of this package? If so let's call the file natural/compare.go too.
Egon ElbreI had trouble figuring out what to call it. There are also package names such as `alphanumeric` or `alphanum` that would fit. I did also consider `natural`, but for some reason it feels like it's not that descriptive and that it's related to ordering strings. Although, since it's called "natural sort order", I think `natural` as a package name is fine as well.
Alan DonovanDone
Thanks. I think compare.go makes the most sense for the file name.
Ah, I missed that comment.
// Implementation only handles numbers [0-9]+, there's no special treatmentIn fewer words:
```
The numeric components consist only of sequences of decimal
digits [0-9] denoting non-negative integers. For example:
```
Done
Simpler and no less efficient: a == "" || b == ""
Done
if !(isdigit(a[0]) && isdigit(b[0])) {
// When at least one of them is not a number,
// we compare them lexicographically.This logic is not consistent with the conceptual explanation based on splitting into digit and non-digit components. Consider a="x0" b="x#1": after the prefix "x" we compare bytes '0' and '#', so `a` is the greater. But the "components" explanation would mean we are comparing the tuples ("x", 0) and ("x#", 1), which results in `a` being the lesser. The Wikipedia article suggests that the conceptual explanation is correct and thus that the logic will need to be adjusted.
Could you add a test case for that input? Thanks.
- Alan Donovan
- Florian Lehner
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alan Donovan (Gerrit)
Alan Donovan added 4 comments![]( "Open in Gerrit")
if adig, bdig := isdigit(a[0]), isdigit(b[0]); !(adig && bdig) {Slightly clearer, and with fewer conditional branches in the common case:
```
adig := isdigit(a[0])
bdig := isdigit(b[0])
// digit vs non-digit?
// The one with the digit is smaller because its non-digit sequence is shorter.
if adig != bdig {
return -b2i(adig)
}
// Inv: adig == bdig
// If both are non-digits, compare lexicographically.
if !adig {
return -b2i(a[0] < b[0])
}
// Inv: adig && bdig
...
func b2i(b bool) int { if b { return 1 } else { return 0 } }
```
// with the digit is smaller, because it's non-digit sequence isits
package naturalnatural_test (+ import), since we're testing only the public API.
Related details
- Egon Elbre
- Florian Lehner
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Egon Elbre (Gerrit)
Egon Elbre uploaded new patchset![]( "Open in Gerrit")
Related details
- Egon Elbre
- Florian Lehner
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Egon Elbre (Gerrit)
Egon Elbre added 3 comments![]( "Open in Gerrit")
if adig, bdig := isdigit(a[0]), isdigit(b[0]); !(adig && bdig) {Slightly clearer, and with fewer conditional branches in the common case:
```
adig := isdigit(a[0])
bdig := isdigit(b[0])// digit vs non-digit?
// The one with the digit is smaller because its non-digit sequence is shorter.
if adig != bdig {
return -b2i(adig)
}
// Inv: adig == bdig// If both are non-digits, compare lexicographically.
if !adig {
return -b2i(a[0] < b[0])
}
// Inv: adig && bdig
...
func b2i(b bool) int { if b { return 1 } else { return 0 } }
```
Ah, this is much nicer.
// with the digit is smaller, because it's non-digit sequence isEgon Elbreits
Done
natural_test (+ import), since we're testing only the public API.
- Alan Donovan
- Florian Lehner
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alan Donovan (Gerrit)
Alan Donovan added 2 comments![]( "Open in Gerrit")
if adig, bdig := isdigit(a[0]), isdigit(b[0]); !(adig && bdig) {Egon ElbreSlightly clearer, and with fewer conditional branches in the common case:
```
adig := isdigit(a[0])
bdig := isdigit(b[0])// digit vs non-digit?
// The one with the digit is smaller because its non-digit sequence is shorter.
if adig != bdig {
return -b2i(adig)
}
// Inv: adig == bdig// If both are non-digits, compare lexicographically.
if !adig {
return -b2i(a[0] < b[0])
}
// Inv: adig && bdig
...
func b2i(b bool) int { if b { return 1 } else { return 0 } }
```
Ah, this is much nicer.
Sorry, I wasn't thinking clearly. Functions named b2i (or btoi) with this signature typically map true to 1 and false to 0, as George Boole himself would have done, rather than returning a signed value, so it is confusing to use the same name for this function.
Let's call it boolToSign. And then I will stop nitpicking and approve the CL.
// b2i converts a boolean to an integer, 1 or -1.
func b2i(b bool) int {
if b {
return 1
} else {
return -1
}
}Sorry, I wasn't thinking clearly. Functions of this name and signaturevery commonly map true to 1 and false to 0, as George Boole himself would have done, rather than returning a signed value, so it is potentially confusing to use the same name here.
Let's call it boolToSign.
Related details
- Egon Elbre
- Florian Lehner
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Egon Elbre (Gerrit)
Egon Elbre uploaded new patchset![]( "Open in Gerrit")
Related details
- Egon Elbre
- Florian Lehner
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Egon Elbre (Gerrit)
Egon Elbre added 2 comments![]( "Open in Gerrit")
if adig, bdig := isdigit(a[0]), isdigit(b[0]); !(adig && bdig) {Egon ElbreSlightly clearer, and with fewer conditional branches in the common case:
```
adig := isdigit(a[0])
bdig := isdigit(b[0])// digit vs non-digit?
// The one with the digit is smaller because its non-digit sequence is shorter.
if adig != bdig {
return -b2i(adig)
}
// Inv: adig == bdig// If both are non-digits, compare lexicographically.
if !adig {
return -b2i(a[0] < b[0])
}
// Inv: adig && bdig
...
func b2i(b bool) int { if b { return 1 } else { return 0 } }
```
Alan DonovanAh, this is much nicer.
Sorry, I wasn't thinking clearly. Functions named b2i (or btoi) with this signature typically map true to 1 and false to 0, as George Boole himself would have done, rather than returning a signed value, so it is confusing to use the same name for this function.
Let's call it boolToSign. And then I will stop nitpicking and approve the CL.
Done
// b2i converts a boolean to an integer, 1 or -1.
func b2i(b bool) int {
if b {
return 1
} else {
return -1
}
}Sorry, I wasn't thinking clearly. Functions of this name and signaturevery commonly map true to 1 and false to 0, as George Boole himself would have done, rather than returning a signed value, so it is potentially confusing to use the same name here.
Let's call it boolToSign.
- Alan Donovan
- Florian Lehner
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Alan Donovan (Gerrit)
Alan Donovan voted and added 1 comment![]( "Open in Gerrit")
Votes added by Alan Donovan
| Auto-Submit | +1 |
| Code-Review | +2 |
| Commit-Queue | +1 |
1 comment
Related details
- Egon Elbre
- Florian Lehner
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Egon Elbre (Gerrit)
Egon Elbre added 3 comments![]( "Open in Gerrit")
package natsortEgon ElbrePerhaps natural.Compare would be a better name for the main function of this package? If so let's call the file natural/compare.go too.
Egon ElbreI had trouble figuring out what to call it. There are also package names such as `alphanumeric` or `alphanum` that would fit. I did also consider `natural`, but for some reason it feels like it's not that descriptive and that it's related to ordering strings. Although, since it's called "natural sort order", I think `natural` as a package name is fine as well.
Alan DonovanDone
Egon ElbreThanks. I think compare.go makes the most sense for the file name.
Ah, I missed that comment.
Done
// Compare implements natural string sorting, where numbers are compared numerically.Egon ElbreThis could use a more precise definition of exactly what it computes.
(What counts as a number? What base? Are leading zeros permitted? It is a weak order: i.e. can two unequal strings Compare equal? etc)
Added examples and clarification on the behaviour.
Done
if !(isdigit(a[0]) && isdigit(b[0])) {
// When at least one of them is not a number,
// we compare them lexicographically.Egon ElbreThis logic is not consistent with the conceptual explanation based on splitting into digit and non-digit components. Consider a="x0" b="x#1": after the prefix "x" we compare bytes '0' and '#', so `a` is the greater. But the "components" explanation would mean we are comparing the tuples ("x", 0) and ("x#", 1), which results in `a` being the lesser. The Wikipedia article suggests that the conceptual explanation is correct and thus that the logic will need to be adjusted.
Could you add a test case for that input? Thanks.
Indeed. I missed this case, should be now fixed.
- Florian Lehner
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
kokoro (Gerrit)
kokoro voted kokoro-CI+1![]( "Open in Gerrit")
Kokoro presubmit build finished with status: SUCCESS
Related details
- Florian Lehner
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Michael Pratt (Gerrit)
Michael Pratt added 1 comment![]( "Open in Gerrit")
Updates #77160```suggestion
Updates golang/go#77160
```
This is why the CL didn't get linked to the issue.
Related details
- Egon Elbre
- Florian Lehner
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Egon Elbre (Gerrit)
Egon Elbre added 1 comment![]( "Open in Gerrit")
Updates #77160```suggestion
Updates golang/go#77160
```This is why the CL didn't get linked to the issue.
- Florian Lehner
- Michael Pratt
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Michael Pratt (Gerrit)
Michael Pratt voted Code-Review+1![]( "Open in Gerrit")
- Alan Donovan
- Egon Elbre
- Florian Lehner
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Michael Pratt (Gerrit)
Michael Pratt voted![]( "Open in Gerrit")
| Auto-Submit | +1 |
| Commit-Queue | +1 |
kokoro (Gerrit)
kokoro voted kokoro-CI+1![]( "Open in Gerrit")
Kokoro presubmit build finished with status: SUCCESS
Related details
- Alan Donovan
- Egon Elbre
- Florian Lehner
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
kokoro-CI-Passes
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Gopher Robot (Gerrit)
Gopher Robot submitted the change![]( "Open in Gerrit")
Unreviewed changes
7 is the latest approved patch-set.
No files were changed between the latest approved patch-set and the submitted one.
Change information
internal/natural: add natural sort order
Natural sort order allows comparing strings such that sequences of digits
are compared numerically rather than lexicographically. For example:
"uint8" < "uint16" < "uint32"
Updates golang/go#77160
- A internal/natural/compare.go
- A internal/natural/compare_test.go
Code-Review: +2 by Alan Donovan, +1 by Michael Pratt
TryBots-Pass: LUCI-TryBot-Result+1 by Go LUCI
kokoro-CI-Passes: kokoro-CI+1 by kokoro
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |