internal/refactor/inline: make fact encoding deterministic

The gob encoding of an analysis fact must be deterministic
(see the "Modular analysis with Facts" section of
golang.org/x/tools/go/analysis).

The inline callee fact was encoded non-deterministically because it
derived data from the randomized iteration order of Go maps. This is
now fixed, and a test asserts that repeatedly analyzing and encoding a
callee produces byte-identical output.

Fixes golang/go#80237

Change-Id: I6fe93314fe841f48013e3f02f147fd5455a74b0f
Reviewed-on: https://go-review.googlesource.com/c/tools/+/802700
Reviewed-by: Carlos Amedee <carlos@golang.org>
Auto-Submit: Alan Donovan <adonovan@google.com>
LUCI-TryBot-Result: golang-scoped@luci-project-accounts.iam.gserviceaccount.com <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Alan Donovan <adonovan@google.com>

internal/moremaps/maps.go

diff --git a/internal/moremaps/maps.go b/internal/moremaps/maps.go
index e4ebee1..a1bae07 100644
--- a/internal/moremaps/maps.go
+++ b/internal/moremaps/maps.go
@@ -90,3 +90,27 @@
 	delete(m, k)
 	return pre != len(m)
 }
+
+// Entry is a key-value pair obtained from a map.
+type Entry[K comparable, V any] struct {
+	Key   K
+	Value V
+}
+
+// Entries returns a new unordered array of the entries of a map.
+func Entries[M ~map[K]V, K comparable, V any](m M) []Entry[K, V] {
+	entries := make([]Entry[K, V], 0, len(m))
+	for k, v := range m {
+		entries = append(entries, Entry[K, V]{k, v})
+	}
+	return entries
+}
+
+// FromEntries returns a new map into which the entries have been inserted in order.
+func FromEntries[K comparable, V any](entries []Entry[K, V]) map[K]V {
+	m := make(map[K]V, len(entries))
+	for _, e := range entries {
+		m[e.Key] = e.Value
+	}
+	return m
+}

internal/refactor/inline/callee.go

diff --git a/internal/refactor/inline/callee.go b/internal/refactor/inline/callee.go
index 68e2844..313e0f7 100644
--- a/internal/refactor/inline/callee.go
+++ b/internal/refactor/inline/callee.go
@@ -8,6 +8,7 @@
 
 import (
 	"bytes"
+	"cmp"
 	"encoding/gob"
 	"fmt"
 	"go/ast"
@@ -18,6 +19,7 @@
 	"strings"
 
 	"golang.org/x/tools/go/types/typeutil"
+	"golang.org/x/tools/internal/moremaps"
 	"golang.org/x/tools/internal/typeparams"
 	"golang.org/x/tools/internal/typesinternal"
 )
@@ -885,6 +887,34 @@
 	return s
 }
 
+var (
+	_ gob.GobEncoder = (*shadowMap)(nil)
+	_ gob.GobDecoder = (*shadowMap)(nil)
+)
+
+// GobEncode implements gob.GobEncoder, encoding the map's entries in a
+// deterministic order so that serialized facts are stable.
+func (s *shadowMap) GobEncode() ([]byte, error) {
+	entries := moremaps.Entries(*s)
+	slices.SortFunc(entries, func(x, y moremaps.Entry[string, int]) int {
+		return cmp.Compare(x.Key, y.Key)
+	})
+	var out bytes.Buffer
+	if err := gob.NewEncoder(&out).Encode(entries); err != nil {
+		return nil, err
+	}
+	return out.Bytes(), nil
+}
+
+func (s *shadowMap) GobDecode(data []byte) error {
+	var entries []moremaps.Entry[string, int]
+	if err := gob.NewDecoder(bytes.NewReader(data)).Decode(&entries); err != nil {
+		return err
+	}
+	*s = moremaps.FromEntries(entries)
+	return nil
+}
+
 // fieldObjs returns a map of each types.Object defined by the given signature
 // to its index in the parameter list. Parameters with missing or blank name
 // are skipped.

internal/refactor/inline/calleefx.go

diff --git a/internal/refactor/inline/calleefx.go b/internal/refactor/inline/calleefx.go
index 001bf61..6dcf0b9 100644
--- a/internal/refactor/inline/calleefx.go
+++ b/internal/refactor/inline/calleefx.go
@@ -10,6 +10,7 @@
 	"go/ast"
 	"go/token"
 	"go/types"
+	"slices"
 
 	"golang.org/x/tools/internal/typesinternal"
 )
@@ -71,14 +72,20 @@
 		// unreferenced by the function body). This lets us
 		// not bother implementing the complete traversal into
 		// control structures.
-		//
-		// TODO(adonovan): add them in a deterministic order.
-		// (This is not a bug but determinism is good.)
-		for _, pinfo := range paramInfos {
+
+		// Sort params by Index for determinism
+		sortedParams := make([]*types.Var, 0, len(paramInfos))
+		for obj, pinfo := range paramInfos {
 			if !pinfo.IsResult && len(pinfo.Refs) > 0 {
-				effect(pinfo.Index)
+				sortedParams = append(sortedParams, obj)
 			}
 		}
+		slices.SortFunc(sortedParams, func(a, b *types.Var) int {
+			return paramInfos[a].Index - paramInfos[b].Index
+		})
+		for _, obj := range sortedParams {
+			effect(paramInfos[obj].Index)
+		}
 	}
 
 	var visitExpr func(n ast.Expr)

internal/refactor/inline/falcon.go

diff --git a/internal/refactor/inline/falcon.go b/internal/refactor/inline/falcon.go
index 037d33b..884a807 100644
--- a/internal/refactor/inline/falcon.go
+++ b/internal/refactor/inline/falcon.go
@@ -13,6 +13,7 @@
 	"go/format"
 	"go/token"
 	"go/types"
+	"slices"
 	"strconv"
 	"strings"
 
@@ -124,11 +125,20 @@
 	// type mapping
 	st.int = st.typename(types.Typ[types.Int])
 	st.any = "interface{}" // don't use "any" as it may be shadowed
-	for obj, info := range st.params {
+
+	// Sort params by Index for determinism
+	sortedParams := make([]*types.Var, 0, len(st.params))
+	for obj := range st.params {
 		if isBasic(obj.Type(), types.IsConstType) {
-			info.FalconType = st.typename(obj.Type())
+			sortedParams = append(sortedParams, obj)
 		}
 	}
+	slices.SortFunc(sortedParams, func(a, b *types.Var) int {
+		return st.params[a].Index - st.params[b].Index
+	})
+	for _, obj := range sortedParams {
+		st.params[obj].FalconType = st.typename(obj.Type())
+	}
 
 	st.stmt(st.decl.Body)