1
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")),
122 forwardSelect(key("hpa-1", "namespace-2"), key("pod-1", "namespace-2")),
123 reverseSelect(key("pod-1", "namespace-1")),
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
219 permutations = indexPermutations(len(tc.ops))
220 } else {
221
222
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
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
259
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
273 useOnceSelector.Matches(labels)
274
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
287 assert.False(t, m.Exists(key("pod-1")))
288 assert.False(t, m.SelectorExists(key("hpa-1")))
289
290
291 m.PutSelector(key("hpa-1"), useOnce(selector("a", "1")))
292 m.Put(key("pod-1"), labels("a", "1"))
293
294
295 assert.True(t, m.Exists(key("pod-1")))
296 assert.True(t, m.SelectorExists(key("hpa-1")))
297
298
299 m.DeleteSelector(key("hpa-1"))
300 m.Delete(key("pod-1"))
301
302
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...)
361 r = append(r[:i], r[i+1:]...)
362 p := permute(append(placed, v), r)
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