Repository: mvdan/sh
Pull request #684 (2021-03-11 20:17:12)

expand: expand.ListEnviron prefers last value
`expand.ListEnviron` does not specify which value is selected when there
are duplicate name=value pairs. The test implied there was last-entry
ordering, but in reality it's lexicographical ordering. This tweaks the
test to better show the as-implemented behavior, even if it's not
guaranteed behavior.

mvdan: Nice find! This was indeed unintentional.

There is a `sort.Strings`, because I wanted to be able to remove duplicates without having to use a map or a double loop to identify duplicates. ListEnviron will be called pretty commonly, so I want to avoid extra allocs or O(n*n) behavior.

That said, the implementation is wrong, as you say. The intent was for the last duplicate element to win, no matter the value. So the sorting shouldn't sort by the entire `name=value` element string, but just `name`. Using `sort.Slice` with a custom comparator should do the trick for that.

Do you want to attempt a fix? Another test case is probably in order, to lock down the intended behavior.
twilly: Hah, I thought the undefined behavior was intentional. :)

I have a stable sort implementation. Let me quickly clean it up and send it to this PR. (Though it does call strings.Index repeatedly, which I haven't analyzed the complexity yet.)
mvdan: You're right, we need the sorting to be stable, too.

More Index calls should be okay for now. In the future, if benchmarks show that it helps, we could consider splitting all elements upfront, so that the sorting and deduping don't have to repeat work.
twilly: Though not directly related to this PR, what was the thinking behind using strings.IndexByte over strings.IndexRune?
mvdan: As far as I know, IndexByte is fine if you're searching for an ASCII character, since you can't possibly hit a false positive with a different utf8-encoded rune.
twilly: > As far as I know, IndexByte is fine if you're searching for an ASCII character, since you can't possibly hit a false positive with a different utf8-encoded rune.

I think you're right about that.

Patch:
diff --git a/expand/environ.go b/expand/environ.go
index 7b89c3d2..c3e08276 100644
--- a/expand/environ.go
+++ b/expand/environ.go
@@ -140,7 +140,8 @@ func (f funcEnviron) Get(name string) Variable {
 func (f funcEnviron) Each(func(name string, vr Variable) bool) {}
 
 // ListEnviron returns an Environ with the supplied variables, in the form
-// "key=value". All variables will be exported.
+// "key=value". All variables will be exported. The last value in pairs is used
+// if multiple values are present.
 //
 // On Windows, where environment variable names are case-insensitive, the
 // resulting variable names will all be uppercase.
@@ -161,7 +162,19 @@ func listEnvironWithUpper(upper bool, pairs ...string) Environ {
 			}
 		}
 	}
-	sort.Strings(list)
+
+	sort.SliceStable(list, func(i, j int) bool {
+		isep := strings.IndexByte(list[i], '=')
+		jsep := strings.IndexByte(list[j], '=')
+		if isep < 0 {
+			isep = 0
+		}
+		if jsep < 0 {
+			jsep = 0
+		}
+		return list[i][:isep] < list[j][:jsep]
+	})
+
 	last := ""
 	for i := 0; i < len(list); {
 		s := list[i]


Test patch:
diff --git a/expand/environ_test.go b/expand/environ_test.go
index e5136e53..afc26c45 100644
--- a/expand/environ_test.go
+++ b/expand/environ_test.go
@@ -32,8 +32,8 @@ func TestListEnviron(t *testing.T) {
 		},
 		{
 			name:  "DuplicateNames",
-			pairs: []string{"A=b", "A=x", "c=", "c=y"},
-			want:  []string{"A=x", "c=y"},
+			pairs: []string{"A=x", "A=b", "c=", "c=y"},
+			want:  []string{"A=b", "c=y"},
 		},
 		{
 			name:  "NoName",