...

Source file src/k8s.io/kubernetes/pkg/controller/util/selectors/bimultimap_test.go

Documentation: k8s.io/kubernetes/pkg/controller/util/selectors

     1  /*
     2  Copyright 2022 The Kubernetes Authors.
     3  
     4  Licensed under the Apache License, Version 2.0 (the "License");
     5  you may not use this file except in compliance with the License.
     6  You may obtain a copy of the License at
     7  
     8      http://www.apache.org/licenses/LICENSE-2.0
     9  
    10  Unless required by applicable law or agreed to in writing, software
    11  distributed under the License is distributed on an "AS IS" BASIS,
    12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13  See the License for the specific language governing permissions and
    14  limitations under the License.
    15  */
    16  
    17  package selectors
    18  
    19  import (
    20  	"fmt"
    21  	"math/rand"
    22  	"testing"
    23  
    24  	"github.com/stretchr/testify/assert"
    25  	pkglabels "k8s.io/apimachinery/pkg/labels"
    26  	"k8s.io/apimachinery/pkg/selection"
    27  )
    28  
    29  func TestAssociations(t *testing.T) {
    30  	cases := []struct {
    31  		name                string
    32  		ops                 []operation
    33  		want                []expectation
    34  		testAllPermutations bool
    35  	}{{
    36  		name: "single association",
    37  		ops: []operation{
    38  			putSelectingObject(key("hpa"), selector("a", "1")),
    39  			putLabeledObject(key("pod"), labels("a", "1")),
    40  		},
    41  		want: []expectation{
    42  			forwardSelect(key("hpa"), key("pod")),
    43  			reverseSelect(key("pod"), key("hpa")),
    44  		},
    45  		testAllPermutations: true,
    46  	}, {
    47  		name: "multiple associations from a selecting object",
    48  		ops: []operation{
    49  			putSelectingObject(key("hpa"), selector("a", "1")),
    50  			putLabeledObject(key("pod-1"), labels("a", "1")),
    51  			putLabeledObject(key("pod-2"), labels("a", "1")),
    52  		},
    53  		want: []expectation{
    54  			forwardSelect(key("hpa"), key("pod-1"), key("pod-2")),
    55  			reverseSelect(key("pod-1"), key("hpa")),
    56  			reverseSelect(key("pod-2"), key("hpa")),
    57  		},
    58  		testAllPermutations: true,
    59  	}, {
    60  		name: "multiple associations to a labeled object",
    61  		ops: []operation{
    62  			putSelectingObject(key("hpa-1"), selector("a", "1")),
    63  			putSelectingObject(key("hpa-2"), selector("a", "1")),
    64  			putLabeledObject(key("pod"), labels("a", "1")),
    65  		},
    66  		want: []expectation{
    67  			forwardSelect(key("hpa-1"), key("pod")),
    68  			forwardSelect(key("hpa-2"), key("pod")),
    69  			reverseSelect(key("pod"), key("hpa-1"), key("hpa-2")),
    70  		},
    71  		testAllPermutations: true,
    72  	}, {
    73  		name: "disjoint association sets",
    74  		ops: []operation{
    75  			putSelectingObject(key("hpa-1"), selector("a", "1")),
    76  			putSelectingObject(key("hpa-2"), selector("a", "2")),
    77  			putLabeledObject(key("pod-1"), labels("a", "1")),
    78  			putLabeledObject(key("pod-2"), labels("a", "2")),
    79  		},
    80  		want: []expectation{
    81  			forwardSelect(key("hpa-1"), key("pod-1")),
    82  			forwardSelect(key("hpa-2"), key("pod-2")),
    83  			reverseSelect(key("pod-1"), key("hpa-1")),
    84  			reverseSelect(key("pod-2"), key("hpa-2")),
    85  		},
    86  		testAllPermutations: true,
    87  	}, {
    88  		name: "separate label cache paths",
    89  		ops: []operation{
    90  			putSelectingObject(key("hpa"), selector("a", "1")),
    91  			putLabeledObject(key("pod-1"), labels("a", "1", "b", "2")),
    92  			putLabeledObject(key("pod-2"), labels("a", "1", "b", "3")),
    93  		},
    94  		want: []expectation{
    95  			forwardSelect(key("hpa"), key("pod-1"), key("pod-2")),
    96  			reverseSelect(key("pod-1"), key("hpa")),
    97  			reverseSelect(key("pod-2"), key("hpa")),
    98  		},
    99  		testAllPermutations: true,
   100  	}, {
   101  		name: "separate selector cache paths",
   102  		ops: []operation{
   103  			putSelectingObject(key("hpa-1"), selector("a", "1")),
   104  			putSelectingObject(key("hpa-2"), selector("b", "2")),
   105  			putLabeledObject(key("pod"), labels("a", "1", "b", "2")),
   106  		},
   107  		want: []expectation{
   108  			forwardSelect(key("hpa-1"), key("pod")),
   109  			forwardSelect(key("hpa-2"), key("pod")),
   110  			reverseSelect(key("pod"), key("hpa-1"), key("hpa-2")),
   111  		},
   112  		testAllPermutations: true,
   113  	}, {
   114  		name: "selection in different namespaces",
   115  		ops: []operation{
   116  			putLabeledObject(key("pod-1", "namespace-1"), labels("a", "1")),
   117  			putLabeledObject(key("pod-1", "namespace-2"), labels("a", "1")),
   118  			putSelectingObject(key("hpa-1", "namespace-2"), selector("a", "1")),
   119  		},
   120  		want: []expectation{
   121  			forwardSelect(key("hpa-1", "namespace-1")), // selects nothing
   122  			forwardSelect(key("hpa-1", "namespace-2"), key("pod-1", "namespace-2")),
   123  			reverseSelect(key("pod-1", "namespace-1")), // selects nothing
   124  			reverseSelect(key("pod-1", "namespace-2"), key("hpa-1", "namespace-2")),
   125  		},
   126  		testAllPermutations: true,
   127  	}, {
   128  		name: "update labeled objects",
   129  		ops: []operation{
   130  			putLabeledObject(key("pod-1"), labels("a", "1")),
   131  			putSelectingObject(key("hpa-1"), selector("a", "2")),
   132  			putLabeledObject(key("pod-1"), labels("a", "2")),
   133  		},
   134  		want: []expectation{
   135  			forwardSelect(key("hpa-1"), key("pod-1")),
   136  			reverseSelect(key("pod-1"), key("hpa-1")),
   137  		},
   138  	}, {
   139  		name: "update selecting objects",
   140  		ops: []operation{
   141  			putSelectingObject(key("hpa-1"), selector("a", "1")),
   142  			putLabeledObject(key("pod-1"), labels("a", "2")),
   143  			putSelectingObject(key("hpa-1"), selector("a", "2")),
   144  		},
   145  		want: []expectation{
   146  			forwardSelect(key("hpa-1"), key("pod-1")),
   147  			reverseSelect(key("pod-1"), key("hpa-1")),
   148  		},
   149  	}, {
   150  		name: "keep only labeled objects",
   151  		ops: []operation{
   152  			putSelectingObject(key("hpa-1"), selector("a", "1")),
   153  			putLabeledObject(key("pod-1"), labels("a", "1")),
   154  			putLabeledObject(key("pod-2"), labels("a", "1")),
   155  			putLabeledObject(key("pod-3"), labels("a", "1")),
   156  			keepOnly(key("pod-1"), key("pod-2")),
   157  		},
   158  		want: []expectation{
   159  			forwardSelect(key("hpa-1"), key("pod-1"), key("pod-2")),
   160  			reverseSelect(key("pod-1"), key("hpa-1")),
   161  			reverseSelect(key("pod-2"), key("hpa-1")),
   162  		},
   163  	}, {
   164  		name: "keep only selecting objects",
   165  		ops: []operation{
   166  			putSelectingObject(key("hpa-1"), selector("a", "1")),
   167  			putSelectingObject(key("hpa-2"), selector("a", "1")),
   168  			putSelectingObject(key("hpa-3"), selector("a", "1")),
   169  			putLabeledObject(key("pod-1"), labels("a", "1")),
   170  			keepOnlySelectors(key("hpa-1"), key("hpa-2")),
   171  		},
   172  		want: []expectation{
   173  			forwardSelect(key("hpa-1"), key("pod-1")),
   174  			forwardSelect(key("hpa-2"), key("pod-1")),
   175  			reverseSelect(key("pod-1"), key("hpa-1"), key("hpa-2")),
   176  		},
   177  	}, {
   178  		name: "put multiple associations and delete all",
   179  		ops: []operation{
   180  			putSelectingObject(key("hpa-1"), selector("a", "1")),
   181  			putSelectingObject(key("hpa-2"), selector("a", "1")),
   182  			putSelectingObject(key("hpa-3"), selector("a", "2")),
   183  			putSelectingObject(key("hpa-4"), selector("b", "1")),
   184  			putLabeledObject(key("pod-1"), labels("a", "1")),
   185  			putLabeledObject(key("pod-2"), labels("a", "2")),
   186  			putLabeledObject(key("pod-3"), labels("a", "1", "b", "1")),
   187  			putLabeledObject(key("pod-4"), labels("a", "2", "b", "1")),
   188  			putLabeledObject(key("pod-5"), labels("b", "1")),
   189  			putLabeledObject(key("pod-6"), labels("b", "2")),
   190  			deleteSelecting(key("hpa-1")),
   191  			deleteSelecting(key("hpa-2")),
   192  			deleteSelecting(key("hpa-3")),
   193  			deleteSelecting(key("hpa-4")),
   194  			deleteLabeled(key("pod-1")),
   195  			deleteLabeled(key("pod-2")),
   196  			deleteLabeled(key("pod-3")),
   197  			deleteLabeled(key("pod-4")),
   198  			deleteLabeled(key("pod-5")),
   199  			deleteLabeled(key("pod-6")),
   200  		},
   201  		want: []expectation{
   202  			emptyMap,
   203  		},
   204  	}, {
   205  		name: "fuzz testing",
   206  		ops: []operation{
   207  			randomOperations(10000),
   208  			deleteAll,
   209  		},
   210  		want: []expectation{
   211  			emptyMap,
   212  		},
   213  	}}
   214  
   215  	for _, tc := range cases {
   216  		var permutations [][]int
   217  		if tc.testAllPermutations {
   218  			// Run test case with all permutations of operations.
   219  			permutations = indexPermutations(len(tc.ops))
   220  		} else {
   221  			// Unless test is order dependent (e.g. includes
   222  			// deletes) or just too big.
   223  			var p []int
   224  			for i := 0; i < len(tc.ops); i++ {
   225  				p = append(p, i)
   226  			}
   227  			permutations = [][]int{p}
   228  		}
   229  		for _, permutation := range permutations {
   230  			name := tc.name + fmt.Sprintf(" permutation %v", permutation)
   231  			t.Run(name, func(t *testing.T) {
   232  				multimap := NewBiMultimap()
   233  				for i := range permutation {
   234  					tc.ops[i](multimap)
   235  					// Run consistency check after every operation.
   236  					err := consistencyCheck(multimap)
   237  					if err != nil {
   238  						t.Fatalf(err.Error())
   239  					}
   240  				}
   241  				for _, expect := range tc.want {
   242  					err := expect(multimap)
   243  					if err != nil {
   244  						t.Errorf("%v %v", tc.name, err)
   245  					}
   246  				}
   247  			})
   248  		}
   249  	}
   250  }
   251  
   252  func TestEfficientAssociation(t *testing.T) {
   253  	useOnceSelector := useOnce(selector("a", "1"))
   254  	m := NewBiMultimap()
   255  	m.PutSelector(key("hpa-1"), useOnceSelector)
   256  	m.Put(key("pod-1"), labels("a", "1"))
   257  
   258  	// Selector is used only during full scan. Second Put will use
   259  	// cached association or explode.
   260  	m.Put(key("pod-2"), labels("a", "1"))
   261  
   262  	err := forwardSelect(key("hpa-1"), key("pod-1"), key("pod-2"))(m)
   263  	if err != nil {
   264  		t.Errorf(err.Error())
   265  	}
   266  }
   267  
   268  func TestUseOnceSelector(t *testing.T) {
   269  	useOnceSelector := useOnce(selector("a", "1"))
   270  	labels := pkglabels.Set(labels("a", "1"))
   271  
   272  	// Use once.
   273  	useOnceSelector.Matches(labels)
   274  	// Use twice.
   275  	defer func() {
   276  		if r := recover(); r == nil {
   277  			t.Errorf("Expected panic when using selector twice.")
   278  		}
   279  	}()
   280  	useOnceSelector.Matches(labels)
   281  }
   282  
   283  func TestObjectsExist(t *testing.T) {
   284  	m := NewBiMultimap()
   285  
   286  	// Nothing exists in the empty map.
   287  	assert.False(t, m.Exists(key("pod-1")))
   288  	assert.False(t, m.SelectorExists(key("hpa-1")))
   289  
   290  	// Adding entries.
   291  	m.PutSelector(key("hpa-1"), useOnce(selector("a", "1")))
   292  	m.Put(key("pod-1"), labels("a", "1"))
   293  
   294  	// Entries exist.
   295  	assert.True(t, m.Exists(key("pod-1")))
   296  	assert.True(t, m.SelectorExists(key("hpa-1")))
   297  
   298  	// Removing the entries.
   299  	m.DeleteSelector(key("hpa-1"))
   300  	m.Delete(key("pod-1"))
   301  
   302  	// They don't exist anymore.
   303  	assert.False(t, m.Exists(key("pod-1")))
   304  	assert.False(t, m.SelectorExists(key("hpa-1")))
   305  }
   306  
   307  type useOnceSelector struct {
   308  	used     bool
   309  	selector pkglabels.Selector
   310  }
   311  
   312  func useOnce(s pkglabels.Selector) pkglabels.Selector {
   313  	return &useOnceSelector{
   314  		selector: s,
   315  	}
   316  }
   317  
   318  func (u *useOnceSelector) Matches(l pkglabels.Labels) bool {
   319  	if u.used {
   320  		panic("useOnceSelector used more than once")
   321  	}
   322  	u.used = true
   323  	return u.selector.Matches(l)
   324  }
   325  
   326  func (u *useOnceSelector) Empty() bool {
   327  	return u.selector.Empty()
   328  }
   329  
   330  func (u *useOnceSelector) String() string {
   331  	return u.selector.String()
   332  }
   333  
   334  func (u *useOnceSelector) Add(r ...pkglabels.Requirement) pkglabels.Selector {
   335  	u.selector = u.selector.Add(r...)
   336  	return u
   337  }
   338  
   339  func (u *useOnceSelector) Requirements() (pkglabels.Requirements, bool) {
   340  	return u.selector.Requirements()
   341  }
   342  
   343  func (u *useOnceSelector) DeepCopySelector() pkglabels.Selector {
   344  	u.selector = u.selector.DeepCopySelector()
   345  	return u
   346  }
   347  
   348  func (u *useOnceSelector) RequiresExactMatch(label string) (value string, found bool) {
   349  	v, f := u.selector.RequiresExactMatch(label)
   350  	return v, f
   351  }
   352  
   353  func indexPermutations(size int) [][]int {
   354  	var permute func([]int, []int) [][]int
   355  	permute = func(placed, remaining []int) (permutations [][]int) {
   356  		if len(remaining) == 0 {
   357  			return [][]int{placed}
   358  		}
   359  		for i, v := range remaining {
   360  			r := append([]int(nil), remaining...) // copy remaining
   361  			r = append(r[:i], r[i+1:]...)         // delete placed index
   362  			p := permute(append(placed, v), r)    // place index and permute
   363  			permutations = append(permutations, p...)
   364  		}
   365  		return
   366  	}
   367  	var remaining []int
   368  	for i := 0; i < size; i++ {
   369  		remaining = append(remaining, i)
   370  	}
   371  	return permute(nil, remaining)
   372  }
   373  
   374  type operation func(*BiMultimap)
   375  
   376  func putLabeledObject(key Key, labels map[string]string) operation {
   377  	return func(m *BiMultimap) {
   378  		m.Put(key, labels)
   379  	}
   380  }
   381  
   382  func putSelectingObject(key Key, selector pkglabels.Selector) operation {
   383  	return func(m *BiMultimap) {
   384  		m.PutSelector(key, selector)
   385  	}
   386  }
   387  
   388  func deleteLabeled(key Key) operation {
   389  	return func(m *BiMultimap) {
   390  		m.Delete(key)
   391  	}
   392  }
   393  
   394  func deleteSelecting(key Key) operation {
   395  	return func(m *BiMultimap) {
   396  		m.DeleteSelector(key)
   397  	}
   398  }
   399  
   400  func deleteAll(m *BiMultimap) {
   401  	for key := range m.labeledObjects {
   402  		m.Delete(key)
   403  	}
   404  	for key := range m.selectingObjects {
   405  		m.DeleteSelector(key)
   406  	}
   407  }
   408  
   409  func keepOnly(keys ...Key) operation {
   410  	return func(m *BiMultimap) {
   411  		m.KeepOnly(keys)
   412  	}
   413  }
   414  
   415  func keepOnlySelectors(keys ...Key) operation {
   416  	return func(m *BiMultimap) {
   417  		m.KeepOnlySelectors(keys)
   418  	}
   419  }
   420  
   421  func randomOperations(times int) operation {
   422  	pods := []Key{
   423  		key("pod-1"),
   424  		key("pod-2"),
   425  		key("pod-3"),
   426  		key("pod-4"),
   427  		key("pod-5"),
   428  		key("pod-6"),
   429  	}
   430  	randomPod := func() Key {
   431  		return pods[rand.Intn(len(pods))]
   432  	}
   433  	labels := []map[string]string{
   434  		labels("a", "1"),
   435  		labels("a", "2"),
   436  		labels("b", "1"),
   437  		labels("b", "2"),
   438  		labels("a", "1", "b", "1"),
   439  		labels("a", "2", "b", "2"),
   440  		labels("a", "3"),
   441  		labels("c", "1"),
   442  	}
   443  	randomLabels := func() map[string]string {
   444  		return labels[rand.Intn(len(labels))]
   445  	}
   446  	hpas := []Key{
   447  		key("hpa-1"),
   448  		key("hpa-2"),
   449  		key("hpa-3"),
   450  	}
   451  	randomHpa := func() Key {
   452  		return hpas[rand.Intn(len(hpas))]
   453  	}
   454  	selectors := []pkglabels.Selector{
   455  		selector("a", "1"),
   456  		selector("b", "1"),
   457  		selector("a", "1", "b", "1"),
   458  		selector("c", "2"),
   459  	}
   460  	randomSelector := func() pkglabels.Selector {
   461  		return selectors[rand.Intn(len(selectors))]
   462  	}
   463  	randomOp := func(m *BiMultimap) {
   464  		switch rand.Intn(4) {
   465  		case 0:
   466  			m.Put(randomPod(), randomLabels())
   467  		case 1:
   468  			m.PutSelector(randomHpa(), randomSelector())
   469  		case 2:
   470  			m.Delete(randomPod())
   471  		case 3:
   472  			m.DeleteSelector(randomHpa())
   473  		}
   474  	}
   475  	return func(m *BiMultimap) {
   476  		for i := 0; i < times; i++ {
   477  			randomOp(m)
   478  		}
   479  	}
   480  }
   481  
   482  type expectation func(*BiMultimap) error
   483  
   484  func forwardSelect(key Key, want ...Key) expectation {
   485  	return func(m *BiMultimap) error {
   486  		got, _ := m.Select(key)
   487  		if !unorderedEqual(want, got) {
   488  			return fmt.Errorf("forward select %v wanted %v. got %v.", key, want, got)
   489  		}
   490  		return nil
   491  	}
   492  }
   493  
   494  func reverseSelect(key Key, want ...Key) expectation {
   495  	return func(m *BiMultimap) error {
   496  		got, _ := m.ReverseSelect(key)
   497  		if !unorderedEqual(want, got) {
   498  			return fmt.Errorf("reverse select %v wanted %v. got %v.", key, want, got)
   499  		}
   500  		return nil
   501  	}
   502  }
   503  
   504  func emptyMap(m *BiMultimap) error {
   505  	if len(m.labeledObjects) != 0 {
   506  		return fmt.Errorf("Found %v labeledObjects. Wanted none.", len(m.labeledObjects))
   507  	}
   508  	if len(m.selectingObjects) != 0 {
   509  		return fmt.Errorf("Found %v selectingObjects. Wanted none.", len(m.selectingObjects))
   510  	}
   511  	if len(m.labeledBySelecting) != 0 {
   512  		return fmt.Errorf("Found %v cached labeledBySelecting associations. Wanted none.", len(m.labeledBySelecting))
   513  	}
   514  	if len(m.selectingByLabeled) != 0 {
   515  		return fmt.Errorf("Found %v cached selectingByLabeled associations. Wanted none.", len(m.selectingByLabeled))
   516  	}
   517  	return nil
   518  }
   519  
   520  func consistencyCheck(m *BiMultimap) error {
   521  	emptyKey := Key{}
   522  	emptyLabelsKey := labelsKey{}
   523  	emptySelectorKey := selectorKey{}
   524  	for k, v := range m.labeledObjects {
   525  		if v == nil {
   526  			return fmt.Errorf("Found nil labeled object for key %q", k)
   527  		}
   528  		if k == emptyKey {
   529  			return fmt.Errorf("Found empty key for labeled object %+v", v)
   530  		}
   531  	}
   532  	for k, v := range m.selectingObjects {
   533  		if v == nil {
   534  			return fmt.Errorf("Found nil selecting object for key %q", k)
   535  		}
   536  		if k == emptyKey {
   537  			return fmt.Errorf("Found empty key for selecting object %+v", v)
   538  		}
   539  	}
   540  	for k, v := range m.labeledBySelecting {
   541  		if v == nil {
   542  			return fmt.Errorf("Found nil labeledBySelecting entry for key %q", k)
   543  		}
   544  		if k == emptySelectorKey {
   545  			return fmt.Errorf("Found empty key for labeledBySelecting object %+v", v)
   546  		}
   547  		for k2, v2 := range v.objects {
   548  			if v2 == nil {
   549  				return fmt.Errorf("Found nil object in labeledBySelecting under keys %q and %q", k, k2)
   550  			}
   551  			if k2 == emptyKey {
   552  				return fmt.Errorf("Found empty key for object in labeledBySelecting under key %+v", k)
   553  			}
   554  		}
   555  		if v.refCount < 1 {
   556  			return fmt.Errorf("Found labeledBySelecting entry with no references (orphaned) under key %q", k)
   557  		}
   558  	}
   559  	for k, v := range m.selectingByLabeled {
   560  		if v == nil {
   561  			return fmt.Errorf("Found nil selectingByLabeled entry for key %q", k)
   562  		}
   563  		if k == emptyLabelsKey {
   564  			return fmt.Errorf("Found empty key for selectingByLabeled object %+v", v)
   565  		}
   566  		for k2, v2 := range v.objects {
   567  			if v2 == nil {
   568  				return fmt.Errorf("Found nil object in selectingByLabeled under keys %q and %q", k, k2)
   569  			}
   570  			if k2 == emptyKey {
   571  				return fmt.Errorf("Found empty key for object in selectingByLabeled under key %+v", k)
   572  			}
   573  		}
   574  		if v.refCount < 1 {
   575  			return fmt.Errorf("Found selectingByLabeled entry with no references (orphaned) under key %q", k)
   576  		}
   577  	}
   578  	return nil
   579  }
   580  
   581  func key(s string, ss ...string) Key {
   582  	if len(ss) > 1 {
   583  		panic("Key requires 1 or 2 parts.")
   584  	}
   585  	k := Key{
   586  		Name: s,
   587  	}
   588  	if len(ss) >= 1 {
   589  		k.Namespace = ss[0]
   590  	}
   591  	return k
   592  }
   593  
   594  func labels(ls ...string) map[string]string {
   595  	if len(ls)%2 != 0 {
   596  		panic("labels requires pairs of strings.")
   597  	}
   598  	ss := make(map[string]string)
   599  	for i := 0; i < len(ls); i += 2 {
   600  		ss[ls[i]] = ls[i+1]
   601  	}
   602  	return ss
   603  }
   604  
   605  func selector(ss ...string) pkglabels.Selector {
   606  	if len(ss)%2 != 0 {
   607  		panic("selector requires pairs of strings.")
   608  	}
   609  	s := pkglabels.NewSelector()
   610  	for i := 0; i < len(ss); i += 2 {
   611  		r, err := pkglabels.NewRequirement(ss[i], selection.Equals, []string{ss[i+1]})
   612  		if err != nil {
   613  			panic(err)
   614  		}
   615  		s = s.Add(*r)
   616  	}
   617  	return s
   618  }
   619  
   620  func unorderedEqual(as, bs []Key) bool {
   621  	if len(as) != len(bs) {
   622  		return false
   623  	}
   624  	aMap := make(map[Key]int)
   625  	for _, a := range as {
   626  		aMap[a]++
   627  	}
   628  	bMap := make(map[Key]int)
   629  	for _, b := range bs {
   630  		bMap[b]++
   631  	}
   632  	if len(aMap) != len(bMap) {
   633  		return false
   634  	}
   635  	for a, count := range aMap {
   636  		if bMap[a] != count {
   637  			return false
   638  		}
   639  	}
   640  	return true
   641  }
   642  

View as plain text