sets: allow unordered types (istio#41371)

This allows us to use Sets for (almost) arbitrary types. The cost is that SortedList must become a function, not a method. Rewrite done using `gofmt -r 'x.SortedList() -> sets.SortedList(x)' -w **/*.go`. The alternative would be to create a duplicate Set type, UnoderedSet; in talking with Rama we both preferred this option.
WillardHu · Oct 13, 2022 · ea42853 · ea42853
1 parent d82a209
commit ea42853
Show file tree

Hide file tree

Showing 32 changed files with 61 additions and 58 deletions.
diff --git a/operator/pkg/controller/istiocontrolplane/istiocontrolplane_controller.go b/operator/pkg/controller/istiocontrolplane/istiocontrolplane_controller.go
@@ -291,14 +291,14 @@ func (r *ReconcileIstioOperator) Reconcile(_ context.Context, request reconcile.
 		}
 
 		finalizers.Delete(finalizer)
-		iop.SetFinalizers(finalizers.SortedList())
+		iop.SetFinalizers(sets.SortedList(finalizers))
 		finalizerError := r.client.Update(context.TODO(), iop)
 		for retryCount := 0; errors.IsConflict(finalizerError) && retryCount < finalizerMaxRetries; retryCount++ {
 			scope.Info("API server conflict during finalizer removal, retrying.")
 			_ = r.client.Get(context.TODO(), request.NamespacedName, iop)
 			finalizers = sets.New(iop.GetFinalizers()...)
 			finalizers.Delete(finalizer)
-			iop.SetFinalizers(finalizers.SortedList())
+			iop.SetFinalizers(sets.SortedList(finalizers))
 			finalizerError = r.client.Update(context.TODO(), iop)
 		}
 		if finalizerError != nil {
@@ -317,7 +317,7 @@ func (r *ReconcileIstioOperator) Reconcile(_ context.Context, request reconcile.
 	} else if !finalizers.Contains(finalizer) {
 		log.Infof("Adding finalizer %v to %v", finalizer, request)
 		finalizers.Insert(finalizer)
-		iop.SetFinalizers(finalizers.SortedList())
+		iop.SetFinalizers(sets.SortedList(finalizers))
 		err := r.client.Update(context.TODO(), iop)
 		if err != nil {
 			if errors.IsNotFound(err) {

diff --git a/pilot/cmd/pilot-discovery/app/options.go b/pilot/cmd/pilot-discovery/app/options.go
@@ -29,7 +29,7 @@ func insecureTLSCipherNames() []string {
 	for _, cipher := range tls.InsecureCipherSuites() {
 		cipherKeys.Insert(cipher.Name)
 	}
-	return cipherKeys.SortedList()
+	return sets.SortedList(cipherKeys)
 }
 
 // secureTLSCipherNames returns a list of secure cipher suite names implemented by crypto/tls.
@@ -38,7 +38,7 @@ func secureTLSCipherNames() []string {
 	for _, cipher := range tls.CipherSuites() {
 		cipherKeys.Insert(cipher.Name)
 	}
-	return cipherKeys.SortedList()
+	return sets.SortedList(cipherKeys)
 }
 
 func validateFlags(serverArgs *bootstrap.PilotArgs) error {

diff --git a/pilot/pkg/config/kube/gateway/context.go b/pilot/pkg/config/kube/gateway/context.go
@@ -93,7 +93,7 @@ func (gc GatewayContext) ResolveGatewayInstances(namespace string, gwsvcs []stri
 					if len(hintPort) > 0 {
 						warnings = append(warnings, fmt.Sprintf(
 							"port %d not found for hostname %q (hint: the service port should be specified, not the workload port. Did you mean one of these ports: %v?)",
-							port, g, hintPort.SortedList()))
+							port, g, sets.SortedList(hintPort)))
 					} else {
 						warnings = append(warnings, fmt.Sprintf("port %d not found for hostname %q", port, g))
 					}
@@ -102,7 +102,7 @@ func (gc GatewayContext) ResolveGatewayInstances(namespace string, gwsvcs []stri
 		}
 	}
 	sort.Strings(warnings)
-	return foundInternal.SortedList(), foundExternal.SortedList(), warnings
+	return sets.SortedList(foundInternal), sets.SortedList(foundExternal), warnings
 }
 
 func (gc GatewayContext) GetService(hostname, namespace string) *model.Service {

diff --git a/pilot/pkg/model/envoyfilter.go b/pilot/pkg/model/envoyfilter.go
@@ -182,7 +182,7 @@ func (efw *EnvoyFilterWrapper) Keys() []string {
 			keys.Insert(patch.Key())
 		}
 	}
-	return keys.SortedList()
+	return sets.SortedList(keys)
 }
 
 func (cpw *EnvoyFilterConfigPatchWrapper) Key() string {

diff --git a/pilot/pkg/model/gateway.go b/pilot/pkg/model/gateway.go
@@ -403,7 +403,7 @@ func GetSNIHostsForServer(server *networking.Server) []string {
 		// do not add hosts, that have already been added
 		sniHosts.Insert(h)
 	}
-	return sniHosts.SortedList()
+	return sets.SortedList(sniHosts)
 }
 
 // CheckDuplicates returns all of the hosts provided that are already known

diff --git a/pilot/pkg/model/proxy_view.go b/pilot/pkg/model/proxy_view.go
@@ -65,5 +65,5 @@ func (v *proxyViewImpl) IsVisible(ep *IstioEndpoint) bool {
 }
 
 func (v *proxyViewImpl) String() string {
-	return strings.Join(v.visible.SortedList(), ",")
+	return strings.Join(sets.SortedList(v.visible), ",")
 }
diff --git a/pilot/pkg/model/push_context.go b/pilot/pkg/model/push_context.go
@@ -1463,7 +1463,7 @@ func (ps *PushContext) initServiceAccounts(env *Environment, services []*Service
 				if len(svc.ServiceAccounts) > 0 {
 					accounts = accounts.Copy().InsertAll(svc.ServiceAccounts...)
 				}
-				sa := spiffe.ExpandWithTrustDomains(accounts, ps.Mesh.TrustDomainAliases).SortedList()
+				sa := sets.SortedList(spiffe.ExpandWithTrustDomains(accounts, ps.Mesh.TrustDomainAliases))
 				key := serviceAccountKey{
 					hostname:  svc.Hostname,
 					namespace: svc.Attributes.Namespace,

diff --git a/pilot/pkg/model/push_context_test.go b/pilot/pkg/model/push_context_test.go
@@ -51,6 +51,7 @@ import (
 	"istio.io/istio/pkg/config/visibility"
 	"istio.io/istio/pkg/test"
 	"istio.io/istio/pkg/test/util/assert"
+	"istio.io/istio/pkg/util/sets"
 )
 
 func TestMergeUpdateRequest(t *testing.T) {
@@ -2641,7 +2642,7 @@ func TestGetHostsFromMeshConfig(t *testing.T) {
 		t.Fatalf("init virtual services failed: %v", err)
 	}
 	got := getHostsFromMeshConfig(ps)
-	assert.Equal(t, []string{"otel.foo.svc.cluster.local"}, got.SortedList())
+	assert.Equal(t, []string{"otel.foo.svc.cluster.local"}, sets.SortedList(got))
 }
 
 // TestGetHostsFromMeshConfigExhaustiveness exhaustiveness check of `getHostsFromMeshConfig`

diff --git a/pilot/pkg/model/telemetry.go b/pilot/pkg/model/telemetry.go
@@ -487,7 +487,7 @@ func (t *Telemetries) telemetryFilters(proxy *Proxy, class networking.ListenerCl
 	}
 
 	m := make([]telemetryFilterConfig, 0, len(allKeys))
-	for _, k := range allKeys.SortedList() {
+	for _, k := range sets.SortedList(allKeys) {
 		p := t.fetchProvider(k)
 		if p == nil {
 			continue

diff --git a/pilot/pkg/networking/core/v1alpha3/listenertest/match.go b/pilot/pkg/networking/core/v1alpha3/listenertest/match.go
@@ -127,7 +127,7 @@ func VerifyListener(t test.Failer, l *listener.Listener, lt ListenerTest) {
 		if lt.TotalMatch {
 			assert.Equal(t, lt.Filters, haveFilters, l.Name+": listener filters should be equal")
 		} else {
-			if missing := sets.New(lt.Filters...).Difference(sets.New(haveFilters...)).SortedList(); len(missing) > 0 {
+			if missing := sets.SortedList(sets.New(lt.Filters...).Difference(sets.New(haveFilters...))); len(missing) > 0 {
 				t.Fatalf("%v: missing listener filters: %v", l.Name, missing)
 			}
 		}
@@ -203,10 +203,10 @@ func VerifyFilterChain(t test.Failer, have *listener.FilterChain, want FilterCha
 			assert.Equal(t, want.HTTPFilters, haveHTTP, context("http should be equal"))
 		}
 	} else {
-		if missing := sets.New(want.NetworkFilters...).Difference(sets.New(haveNetwork...)).SortedList(); len(missing) > 0 {
+		if missing := sets.SortedList(sets.New(want.NetworkFilters...).Difference(sets.New(haveNetwork...))); len(missing) > 0 {
 			t.Fatalf("%v/%v: missing network filters: %v, have %v", have.Name, haveType, missing, haveNetwork)
 		}
-		if missing := sets.New(want.HTTPFilters...).Difference(sets.New(haveHTTP...)).SortedList(); len(missing) > 0 {
+		if missing := sets.SortedList(sets.New(want.HTTPFilters...).Difference(sets.New(haveHTTP...))); len(missing) > 0 {
 			t.Fatalf("%v/%v: missing network filters: %v, have %v", have.Name, haveType, missing, haveHTTP)
 		}
 	}

diff --git a/pilot/pkg/networking/grpcgen/lds.go b/pilot/pkg/networking/grpcgen/lds.go
@@ -286,7 +286,7 @@ func buildOutboundListeners(node *model.Proxy, push *model.PushContext, filter l
 			continue
 		}
 		// we must duplicate the listener for every requested host - grpc may have watches for both foo and foo.ns
-		for _, matchedHost := range match.RequestedNames.SortedList() {
+		for _, matchedHost := range sets.SortedList(match.RequestedNames) {
 			for _, p := range sv.Ports {
 				sPort := strconv.Itoa(p.Port)
 				if !match.includesPort(sPort) {

diff --git a/pilot/pkg/serviceregistry/util/workloadinstances/index.go b/pilot/pkg/serviceregistry/util/workloadinstances/index.go
@@ -18,6 +18,7 @@ import (
 	"sync"
 
 	"istio.io/istio/pilot/pkg/model"
+	"istio.io/istio/pkg/util/sets"
 )
 
 // Index reprensents an index over workload instances from workload entries.
@@ -113,7 +114,7 @@ func (i *index) GetByIP(ip string) []*model.WorkloadInstance {
 		return nil
 	}
 	instances := make([]*model.WorkloadInstance, 0, len(keys))
-	for _, key := range keys.SortedList() {
+	for _, key := range sets.SortedList(keys) {
 		if instance, exists := i.keyToInstance[key]; exists {
 			instances = append(instances, instance)
 		}

diff --git a/pilot/pkg/xds/cds_test.go b/pilot/pkg/xds/cds_test.go
@@ -218,7 +218,7 @@ func TestSAN(t *testing.T) {
 				for _, n := range tl.GetCommonTlsContext().GetCombinedValidationContext().GetDefaultValidationContext().GetMatchSubjectAltNames() {
 					names.Insert(n.GetExact())
 				}
-				assert.Equal(t, names.SortedList(), sets.New(sans...).SortedList())
+				assert.Equal(t, sets.SortedList(names), sets.SortedList(sets.New(sans...)))
 			}
 			// Run multiple assertions to verify idempotency; previous versions had issues here.
 			for i := 0; i < 2; i++ {

diff --git a/pilot/pkg/xds/delta.go b/pilot/pkg/xds/delta.go
@@ -480,7 +480,7 @@ func (s *DiscoveryServer) pushDeltaXds(con *Connection,
 		// similar to sotw
 		subscribed := sets.New(w.ResourceNames...)
 		subscribed.DeleteAll(currentResources...)
-		resp.RemovedResources = subscribed.SortedList()
+		resp.RemovedResources = sets.SortedList(subscribed)
 	}
 	if len(resp.RemovedResources) > 0 {
 		deltaLog.Debugf("ADS:%v REMOVE for node:%s %v", v3.GetShortType(w.TypeUrl), con.conID, resp.RemovedResources)
@@ -563,7 +563,7 @@ func deltaWatchedResources(existing []string, request *discovery.DeltaDiscoveryR
 	res := sets.New(existing...)
 	res.InsertAll(request.ResourceNamesSubscribe...)
 	res.DeleteAll(request.ResourceNamesUnsubscribe...)
-	return res.SortedList()
+	return sets.SortedList(res)
 }
 
 func extractNames(res []*discovery.Resource) []string {

diff --git a/pilot/pkg/xds/deltatest.go b/pilot/pkg/xds/deltatest.go
@@ -104,12 +104,12 @@ func (s *DiscoveryServer) compareDiff(
 	}
 
 	// BUGS
-	extraDeletes := gotDeleted.Difference(wantDeleted).SortedList()
-	missedDeletes := wantDeleted.Difference(gotDeleted).SortedList()
-	missedChanges := wantChanged.Difference(gotChanged).SortedList()
+	extraDeletes := sets.SortedList(gotDeleted.Difference(wantDeleted))
+	missedDeletes := sets.SortedList(wantDeleted.Difference(gotDeleted))
+	missedChanges := sets.SortedList(wantChanged.Difference(gotChanged))
 
 	// Optimization Potential
-	extraChanges := gotChanged.Difference(wantChanged).Difference(knownOptimizationGaps).SortedList()
+	extraChanges := sets.SortedList(gotChanged.Difference(wantChanged).Difference(knownOptimizationGaps))
 	if len(delta.Subscribed) > 0 {
 		// Delta is configured to build only the request resources. Make sense we didn't build anything extra
 		if !wantChanged.SupersetOf(gotChanged) {

diff --git a/pilot/pkg/xds/eds_test.go b/pilot/pkg/xds/eds_test.go
@@ -360,8 +360,8 @@ func TestEDSUnhealthyEndpoints(t *testing.T) {
 		// Validate that endpoints are pushed.
 		lbe := adscon.GetEndpoints()["outbound|53||unhealthy.svc.cluster.local"]
 		eh, euh := xdstest.ExtractHealthEndpoints(lbe)
-		gotHealthy := sets.New(eh...).SortedList()
-		gotUnhealthy := sets.New(euh...).SortedList()
+		gotHealthy := sets.SortedList(sets.New(eh...))
+		gotUnhealthy := sets.SortedList(sets.New(euh...))
 		if !reflect.DeepEqual(gotHealthy, healthy) {
 			t.Fatalf("did not get expected endpoints: got %v, want %v", gotHealthy, healthy)
 		}
@@ -599,7 +599,7 @@ func TestEndpointFlipFlops(t *testing.T) {
 			if shard, ok := s.Discovery.Env.EndpointIndex.ShardsForService("flipflop.com", ""); !ok {
 				t.Fatalf("Expected service key %s to be present in EndpointIndex. But missing %v", "flipflop.com", s.Discovery.Env.EndpointIndex.Shardz())
 			} else {
-				assert.Equal(t, shard.ServiceAccounts.SortedList(), []string{tt.newSa})
+				assert.Equal(t, sets.SortedList(shard.ServiceAccounts), []string{tt.newSa})
 			}
 		})
 	}

diff --git a/pkg/config/mesh/mesh.go b/pkg/config/mesh/mesh.go
@@ -243,7 +243,7 @@ func ApplyMeshConfig(yaml string, defaultConfig *meshconfig.MeshConfig) (*meshco
 		}
 	}
 
-	defaultConfig.TrustDomainAliases = sets.New(append(defaultConfig.TrustDomainAliases, prevTrustDomainAliases...)...).SortedList()
+	defaultConfig.TrustDomainAliases = sets.SortedList(sets.New(append(defaultConfig.TrustDomainAliases, prevTrustDomainAliases...)...))
 
 	warn, err := validation.ValidateMeshConfig(defaultConfig)
 	if err != nil {

diff --git a/pkg/config/validation/validation.go b/pkg/config/validation/validation.go
@@ -584,11 +584,11 @@ func validateTLSOptions(tls *networking.ServerTLSSettings) (v Validation) {
 	}
 
 	if len(invalidCiphers) > 0 {
-		v = appendWarningf(v, "ignoring invalid cipher suites: %v", invalidCiphers.SortedList())
+		v = appendWarningf(v, "ignoring invalid cipher suites: %v", sets.SortedList(invalidCiphers))
 	}
 
 	if len(duplicateCiphers) > 0 {
-		v = appendWarningf(v, "ignoring duplicate cipher suites: %v", duplicateCiphers.SortedList())
+		v = appendWarningf(v, "ignoring duplicate cipher suites: %v", sets.SortedList(duplicateCiphers))
 	}
 
 	if tls.Mode == networking.ServerTLSSettings_ISTIO_MUTUAL {

diff --git a/pkg/kube/namespace/filter.go b/pkg/kube/namespace/filter.go
@@ -131,8 +131,8 @@ func (d *discoveryNamespacesFilter) SelectorsChanged(
 	}
 
 	oldDiscoveryNamespaces := d.discoveryNamespaces
-	selectedNamespaces = newDiscoveryNamespaces.Difference(oldDiscoveryNamespaces).SortedList()
-	deselectedNamespaces = oldDiscoveryNamespaces.Difference(newDiscoveryNamespaces).SortedList()
+	selectedNamespaces = sets.SortedList(newDiscoveryNamespaces.Difference(oldDiscoveryNamespaces))
+	deselectedNamespaces = sets.SortedList(oldDiscoveryNamespaces.Difference(newDiscoveryNamespaces))
 
 	// update filter state
 	d.discoveryNamespaces = newDiscoveryNamespaces

diff --git a/pkg/test/framework/components/echo/config/builder.go b/pkg/test/framework/components/echo/config/builder.go
@@ -27,6 +27,7 @@ import (
 	"istio.io/istio/pkg/test/framework/resource/config"
 	"istio.io/istio/pkg/test/framework/resource/config/apply"
 	"istio.io/istio/pkg/test/scopes"
+	"istio.io/istio/pkg/util/sets"
 )
 
 // Builder of configuration.
@@ -251,7 +252,7 @@ func (b *Builder) checkMissing(s Source) {
 	tpl := s.TemplateOrFail(b.t)
 	missing := tpl.MissingParams(s.Params())
 	if missing.Len() > 0 {
-		b.t.Fatalf("config template requires missing params: %v", missing.SortedList())
+		b.t.Fatalf("config template requires missing params: %v", sets.SortedList(missing))
 	}
 }
 

diff --git a/pkg/test/framework/components/echo/namespacedname.go b/pkg/test/framework/components/echo/namespacedname.go
@@ -92,5 +92,5 @@ func (n NamespacedNames) uniqueSortedNames(getName func(NamespacedName) string)
 		name := getName(nn)
 		set.Insert(name)
 	}
-	return set.SortedList()
+	return sets.SortedList(set)
 }
diff --git a/pkg/util/sets/set.go b/pkg/util/sets/set.go
@@ -19,18 +19,18 @@ import (
 	"golang.org/x/exp/slices"
 )
 
-type Set[T constraints.Ordered] map[T]struct{}
+type Set[T comparable] map[T]struct{}
 
 type String = Set[string]
 
 // NewWithLength returns an empty Set with the given capacity.
 // It's only a hint, not a limitation.
-func NewWithLength[T constraints.Ordered](l int) Set[T] {
+func NewWithLength[T comparable](l int) Set[T] {
 	return make(Set[T], l)
 }
 
 // New creates a new Set with the given items.
-func New[T constraints.Ordered](items ...T) Set[T] {
+func New[T comparable](items ...T) Set[T] {
 	s := NewWithLength[T](len(items))
 	return s.InsertAll(items...)
 }
@@ -149,7 +149,7 @@ func (s Set[T]) UnsortedList() []T {
 }
 
 // SortedList returns the slice with contents sorted.
-func (s Set[T]) SortedList() []T {
+func SortedList[T constraints.Ordered](s Set[T]) []T {
 	res := s.UnsortedList()
 	slices.Sort(res)
 	return res

diff --git a/pkg/util/sets/set_test.go b/pkg/util/sets/set_test.go
@@ -104,13 +104,13 @@ func TestSupersetOf(t *testing.T) {
 	s2 := New(elements2...)
 
 	if !s1.SupersetOf(s2) {
-		t.Errorf("%v should be superset of %v", s1.SortedList(), s2.SortedList())
+		t.Errorf("%v should be superset of %v", SortedList(s1), SortedList(s2))
 	}
 
 	s3 := New[string]()
 	if !New[string]().SupersetOf(s3) {
-		fmt.Printf("%q\n", s3.SortedList()[0])
-		t.Errorf("%v should be superset of empty set", s1.SortedList())
+		fmt.Printf("%q\n", SortedList(s3)[0])
+		t.Errorf("%v should be superset of empty set", SortedList(s1))
 	}
 }
 
@@ -179,7 +179,7 @@ func TestMerge(t *testing.T) {
 
 	for _, tc := range cases {
 		got := tc.s1.Merge(tc.s2)
-		assert.Equal(t, tc.expected, got.SortedList())
+		assert.Equal(t, tc.expected, SortedList(got))
 	}
 }
 
@@ -249,7 +249,7 @@ func BenchmarkSet(b *testing.B) {
 			b.StopTimer()
 			s := New(sortOrder...)
 			b.StartTimer()
-			s.SortedList()
+			SortedList(s)
 		}
 	})
 }
diff --git a/security/pkg/nodeagent/cache/secretcache.go b/security/pkg/nodeagent/cache/secretcache.go
@@ -773,7 +773,7 @@ func (sc *SecretManagerClient) mergeConfigTrustBundle(rootCerts []string) []byte
 		anchors.Insert(cert)
 	}
 	anchorBytes := []byte{}
-	for _, cert := range anchors.SortedList() {
+	for _, cert := range sets.SortedList(anchors) {
 		anchorBytes = pkiutil.AppendCertByte(anchorBytes, []byte(cert))
 	}
 	return anchorBytes

diff --git a/security/pkg/nodeagent/caclient/providers/google-cas/client.go b/security/pkg/nodeagent/caclient/providers/google-cas/client.go
@@ -136,7 +136,7 @@ func (r *GoogleCASClient) GetRootCertBundle() ([]string, error) {
 		rootCertSet.Insert(rootCert)
 	}
 
-	return rootCertSet.SortedList(), nil
+	return sets.SortedList(rootCertSet), nil
 }
 
 func (r *GoogleCASClient) Close() {

diff --git a/tests/integration/pilot/common/routing.go b/tests/integration/pilot/common/routing.go
@@ -1174,7 +1174,7 @@ spec:
 		templateVars: func(src echo.Callers, dests echo.Instances) map[string]any {
 			// Test all cipher suites, including a fake one. Envoy should accept all of the ones on the "valid" list,
 			// and control plane should filter our invalid one.
-			return templateParams(protocol.HTTPS, src, dests, append(security.ValidCipherSuites.SortedList(), "fake"))
+			return templateParams(protocol.HTTPS, src, dests, append(sets.SortedList(security.ValidCipherSuites), "fake"))
 		},
 		setupOpts: fqdnHostHeader,
 		opts: echo.CallOptions{
@@ -2125,7 +2125,7 @@ var ConsistentHostChecker echo.Checker = func(result echo.CallResult, _ error) e
 		hostnames[i] = r.Hostname
 	}
 	scopes.Framework.Infof("requests landed on hostnames: %v", hostnames)
-	unique := sets.New(hostnames...).SortedList()
+	unique := sets.SortedList(sets.New(hostnames...))
 	if len(unique) != 1 {
 		return fmt.Errorf("expected only one destination, got: %v", unique)
 	}