Repository: knative/pkg
Pull request #1925 (2020-11-24 15:42:04)

Apply multiple bindings to the same subject
Fixes https://github.com/knative/pkg/issues/1786.

cc @mattmoor @n3wscott 

knative-prow-robot: Skipping CI for Draft Pull Request.
If you want CI signal for your change, please convert it to an actual PR.
You can still manually trigger a test run with `/test all`
knative-prow-robot: [APPROVALNOTIFIER] This PR is **NOT APPROVED**

This pull-request has been approved by: *<a href="https://github.com/knative/pkg/pull/1925#" title="Author self-approved">glyn</a>*
To complete the [pull request process](https://git.k8s.io/community/contributors/guide/owners.md#the-code-review-process), please assign **tcnghia** after the PR has been reviewed.
You can assign the PR to them by writing `/assign @tcnghia` in a comment when ready.

The full list of commands accepted by this bot can be found [here](https://go.k8s.io/bot-commands?repo=knative%2Fpkg).

<details open>
Needs approval from an approver in each of these files:

- **[webhook/OWNERS](https://github.com/knative/pkg/blob/master/webhook/OWNERS)**

Approvers can indicate their approval by writing `/approve` in a comment
Approvers can cancel approval by writing `/approve cancel` in a comment
</details>
<!-- META={"approvers":["tcnghia"]} -->
codecov[bot]: # [Codecov](https://codecov.io/gh/knative/pkg/pull/1925?src=pr&el=h1) Report
> Merging [#1925](https://codecov.io/gh/knative/pkg/pull/1925?src=pr&el=desc) (6880629) into [master](https://codecov.io/gh/knative/pkg/commit/49e55c9eb816c9077558d813509a4cbe603cf8ff?el=desc) (49e55c9) will **increase** coverage by `0.06%`.
> The diff coverage is `90.00%`.

[![Impacted file tree graph](https://codecov.io/gh/knative/pkg/pull/1925/graphs/tree.svg?width=650&height=150&src=pr&token=rlqpDnfxbO)](https://codecov.io/gh/knative/pkg/pull/1925?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master    #1925      +/-   ##
==========================================
+ Coverage   69.45%   69.52%   +0.06%     
==========================================
  Files         207      207              
  Lines        8762     8775      +13     
==========================================
+ Hits         6086     6101      +15     
+ Misses       2403     2402       -1     
+ Partials      273      272       -1     
```


| [Impacted Files](https://codecov.io/gh/knative/pkg/pull/1925?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [webhook/psbinding/psbinding.go](https://codecov.io/gh/knative/pkg/pull/1925/diff?src=pr&el=tree#diff-d2ViaG9vay9wc2JpbmRpbmcvcHNiaW5kaW5nLmdv) | `84.39% <79.16%> (-1.32%)` | :arrow_down: |
| [webhook/psbinding/index.go](https://codecov.io/gh/knative/pkg/pull/1925/diff?src=pr&el=tree#diff-d2ViaG9vay9wc2JpbmRpbmcvaW5kZXguZ28=) | `100.00% <100.00%> (ø)` | |
| [test/gcs/mock/mock.go](https://codecov.io/gh/knative/pkg/pull/1925/diff?src=pr&el=tree#diff-dGVzdC9nY3MvbW9jay9tb2NrLmdv) | `91.39% <0.00%> (+1.07%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/knative/pkg/pull/1925?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/knative/pkg/pull/1925?src=pr&el=footer). Last update [49e55c9...5dbabdf](https://codecov.io/gh/knative/pkg/pull/1925?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

mattmoor: This generally seems reasonable to me.
glyn: @vagababov Hi. The PR is functionally complete. I'm going to beef up the exact and inexact reverse index tests. Meanwhile, PTAL.
glyn: Note: the coverage of `psbinding.go` has decreased only because code was factored out and the uncovered lines are now a larger proportion of the total.
glyn: @scothis PTAL and see if this fixes the downstream problem.
glyn: >  I'm going to beef up the exact and inexact reverse index tests.

Done.


knative-prow-robot: New changes are detected. LGTM label has been removed.

Patch:
diff --git a/webhook/psbinding/index.go b/webhook/psbinding/index.go
index 2ad47b10e..1a4dd49cc 100644
--- a/webhook/psbinding/index.go
+++ b/webhook/psbinding/index.go
@@ -7,7 +7,7 @@ You may obtain a copy of the License at
 
     http://www.apache.org/licenses/LICENSE-2.0
 
-Unless requ ired by applicable law or agreed to in writing, software
+Unless required by applicable law or agreed to in writing, software
 distributed under the License is distributed on an "AS IS" BASIS,
 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 See the License for the specific language governing permissions and
@@ -16,7 +16,11 @@ limitations under the License.
 
 package psbinding
 
-import "k8s.io/apimachinery/pkg/labels"
+import (
+	"sync"
+
+	"k8s.io/apimachinery/pkg/labels"
+)
 
 // exactKey is the type for keys that match exactly.
 type exactKey struct {
@@ -28,17 +32,16 @@ type exactKey struct {
 
 // exactMatcher is our reverse index from subjects to the Bindings that apply to
 // them.
-type exactMatcher map[exactKey]Bindable
+type exactMatcher map[exactKey][]Bindable
 
-// Add writes a key into the reverse index.
-func (em exactMatcher) Add(key exactKey, b Bindable) {
-	em[key] = b
+// add associates a Binding with a key in the reverse index.
+func (em exactMatcher) add(key exactKey, b Bindable) {
+	em[key] = append(em[key], b)
 }
 
-// Get fetches the key from the reverse index, if present.
-func (em exactMatcher) Get(key exactKey) (bindable Bindable, present bool) {
-	b, ok := em[key]
-	return b, ok
+// get fetches the key from the reverse index, if present.
+func (em exactMatcher) get(key exactKey) []Bindable {
+	return em[key]
 }
 
 // inexactKey is the type for keys that match inexactly (via selector)
@@ -58,8 +61,8 @@ type pair struct {
 // them.
 type inexactMatcher map[inexactKey][]pair
 
-// Add writes a key into the reverse index.
-func (im inexactMatcher) Add(key inexactKey, selector labels.Selector, b Bindable) {
+// add writes a key into the reverse index.
+func (im inexactMatcher) add(key inexactKey, selector labels.Selector, b Bindable) {
 	pl := im[key]
 	pl = append(pl, pair{
 		selector: selector,
@@ -68,14 +71,78 @@ func (im inexactMatcher) Add(key inexactKey, selector labels.Selector, b Bindabl
 	im[key] = pl
 }
 
-// Get fetches the key from the reverse index, if present.
-func (im inexactMatcher) Get(key inexactKey, ls labels.Set) (bindable Bindable, present bool) {
-	// Iterate over the list of pairs matched for this GK + namespace and return the first
-	// Bindable that matches our selector.
+// get fetches the key from the reverse index, if present.
+func (im inexactMatcher) get(key inexactKey, ls labels.Set) []Bindable {
+	found := []Bindable{}
+	// Iterate over the list of pairs matched for this GK + namespace and collect the
+	// Bindables that matches our selector.
 	for _, p := range im[key] {
 		if p.selector.Matches(ls) {
-			return p.sb, true
+			found = append(found, p.sb)
 		}
 	}
-	return nil, false
+	return found
+}
+
+// index is a collection of Bindables indexed by their subject resources.
+type index struct {
+	// lock protects access to exact and inexact
+	lock    sync.RWMutex
+	exact   exactMatcher
+	inexact inexactMatcher
+}
+
+// indexBuilder allows an index to be built atomically
+type indexBuilder struct {
+	exact   exactMatcher
+	inexact inexactMatcher
+}
+
+// newIndexBuilder constructs a new IndexBuilder.
+func newIndexBuilder() *indexBuilder {
+	return &indexBuilder{
+		exact:   make(exactMatcher),
+		inexact: make(inexactMatcher),
+	}
+}
+
+// associate associates a resource with a given exact key with a given Bindable.
+func (ib *indexBuilder) associate(key exactKey, fb Bindable) *indexBuilder {
+	ib.exact.add(key, fb)
+	return ib
+}
+
+// associateSelection associates resources with the given inexact key and labels matching the given selector with a given Bindable.
+func (ib *indexBuilder) associateSelection(inexactKey inexactKey, selector labels.Selector, fb Bindable) *indexBuilder {
+	ib.inexact.add(inexactKey, selector, fb)
+	return ib
+}
+
+// build sets the given index to the built value.
+func (ib *indexBuilder) build(index *index) {
+	index.setIndex(ib.exact, ib.inexact)
+}
+
+// setIndex replaces the index atomically with the given matchers.
+func (idx *index) setIndex(exact exactMatcher, inexact inexactMatcher) {
+	idx.lock.Lock()
+	defer idx.lock.Unlock()
+	idx.exact = exact
+	idx.inexact = inexact
+}
+
+// lookUp returns the Bindables associated with a resource with the given group, kind, namespace, name, and labels.
+func (idx *index) lookUp(key exactKey, labels labels.Set) []Bindable {
+	idx.lock.RLock()
+	defer idx.lock.RUnlock()
+
+	exactMatches := idx.exact.get(key)
+
+	inexactMatches := idx.inexact.get(inexactKey{
+		Group:     key.Group,
+		Kind:      key.Kind,
+		Namespace: key.Namespace,
+	}, labels)
+
+	return append(exactMatches, inexactMatches...)
 }
diff --git a/webhook/psbinding/psbinding.go b/webhook/psbinding/psbinding.go
index 741859058..5a3a6b258 100644
--- a/webhook/psbinding/psbinding.go
+++ b/webhook/psbinding/psbinding.go
@@ -23,7 +23,6 @@ import (
 	"fmt"
 	"sort"
 	"strings"
-	"sync"
 
 	"github.com/markbates/inflect"
 	"go.uber.org/zap"
@@ -117,10 +116,7 @@ type Reconciler struct {
 
 	selector metav1.LabelSelector
 
-	// lock protects access to exact and inexact
-	lock    sync.RWMutex
-	exact   exactMatcher
-	inexact inexactMatcher
+	index index
 }
 
 var _ controller.Reconciler = (*Reconciler)(nil)
@@ -197,56 +193,47 @@ func (ac *Reconciler) Admit(ctx context.Context, request *admissionv1.AdmissionR
 		return webhook.MakeErrorStatus("unable to decode object: %v", err)
 	}
 
-	// Look up the Bindable for this resource.
-	fb := func() Bindable {
-		ac.lock.RLock()
-		defer ac.lock.RUnlock()
-
-		// Always try to find an exact match first.
-		if sb, ok := ac.exact.Get(exactKey{
-			Group:     request.Kind.Group,
-			Kind:      request.Kind.Kind,
-			Namespace: request.Namespace,
-			Name:      orig.Name,
-		}); ok {
-			return sb
-		}
-
-		// Next look for inexact matches.
-		if sb, ok := ac.inexact.Get(inexactKey{
-			Group:     request.Kind.Group,
-			Kind:      request.Kind.Kind,
-			Namespace: request.Namespace,
-		}, labels.Set(orig.Labels)); ok {
-			return sb
-		}
-		return nil
-	}()
-	if fb == nil {
+	// Look up the Bindables for this resource.
+	fbs := ac.index.lookUp(exactKey{
+		Group:     request.Kind.Group,
+		Kind:      request.Kind.Kind,
+		Namespace: request.Namespace,
+		Name:      orig.Name},
+		labels.Set(orig.Labels))
+	if len(fbs) == 0 {
 		// This doesn't apply!
 		return &admissionv1.AdmissionResponse{Allowed: true}
 	}
 
-	// Callback into the user's code to setup the context with additional
-	// information needed to perform the mutation.
-	if ac.WithContext != nil {
-		var err error
-		ctx, err = ac.WithContext(ctx, fb)
-		if err != nil {
-			return webhook.MakeErrorStatus("unable to setup binding context: %v", err)
+	// Copy the subject state.
+	mutated := orig.DeepCopy()
+
+	// Apply the Bindables to the copy of the subject state. If conflicts occur, for example because multiple Bindables
+	// make incompatible changes, the reconciler will attempt to correct the state later.
+	for _, fb := range fbs {
+		var bindingContext context.Context
+		// Callback into the user's code to setup the context with additional
+		// information needed to perform the mutation.
+		if ac.WithContext != nil {
+			var err error
+			bindingContext, err = ac.WithContext(ctx, fb)
+			if err != nil {
+				return webhook.MakeErrorStatus("unable to setup binding context: %v", err)
+			}
+		} else {
+			bindingContext = ctx
 		}
-	}
 
-	// Mutate a copy according to the deletion state of the Bindable.
-	delta := orig.DeepCopy()
-	if fb.GetDeletionTimestamp() != nil {
-		fb.Undo(ctx, delta)
-	} else {
-		fb.Do(ctx, delta)
+		// Mutate the copy of the subject state according to the deletion state of the Bindable.
+		if fb.GetDeletionTimestamp() != nil {
+			fb.Undo(bindingContext, mutated)
+		} else {
+			fb.Do(bindingContext, mutated)
+		}
 	}
 
 	// Synthesize a patch from the changes and return it in our AdmissionResponse
-	patchBytes, err := duck.CreateBytePatch(orig, delta)
+	patchBytes, err := duck.CreateBytePatch(orig, mutated)
 	if err != nil {
 		return webhook.MakeErrorStatus("unable to create patch with binding: %v", err)
 	}
@@ -270,8 +257,8 @@ func (ac *Reconciler) reconcileMutatingWebhook(ctx context.Context, caCert []byt
 	if err != nil {
 		return err
 	}
-	exact := make(exactMatcher, len(fbs))
-	inexact := make(inexactMatcher, len(fbs))
+
+	ib := newIndexBuilder()
 	for _, fb := range fbs {
 		ref := fb.GetSubject()
 		gv, err := schema.ParseGroupVersion(ref.APIVersion)
@@ -290,32 +277,27 @@ func (ac *Reconciler) reconcileMutatingWebhook(ctx context.Context, caCert []byt
 		gks[gk] = set
 
 		if ref.Name != "" {
-			exact.Add(exactKey{
+			ib.associate(exactKey{
 				Group:     gk.Group,
 				Kind:      gk.Kind,
 				Namespace: ref.Namespace,
-				Name:      ref.Name,
-			}, fb)
+				Name:      ref.Name},
+				fb)
 		} else {
 			selector, err := metav1.LabelSelectorAsSelector(ref.Selector)
 			if err != nil {
 				return err
 			}
-			inexact.Add(inexactKey{
+			ib.associateSelection(inexactKey{
 				Group:     gk.Group,
 				Kind:      gk.Kind,
-				Namespace: ref.Namespace,
-			}, selector, fb)
+				Namespace: ref.Namespace},
+				selector, fb)
 		}
 	}
 
-	// Update our indices
-	func() {
-		ac.lock.Lock()
-		defer ac.lock.Unlock()
-		ac.exact = exact
-		ac.inexact = inexact
-	}()
+	// Update the index.
+	ib.build(&ac.index)
 
 	// After we've updated our indices, bail out unless we are the leader.
 	// Only the leader should be mutating the webhook.


Test patch:
diff --git a/configmap/informed_watcher_test.go b/configmap/informed_watcher_test.go
index 801825226..fa2057eef 100644
--- a/configmap/informed_watcher_test.go
+++ b/configmap/informed_watcher_test.go
@@ -20,6 +20,7 @@ import (
 	"context"
 	"sync"
 	"testing"
+	"time"
 
 	corev1 "k8s.io/api/core/v1"
 	"k8s.io/apimachinery/pkg/api/equality"
@@ -27,6 +28,7 @@ import (
 	"k8s.io/apimachinery/pkg/labels"
 	"k8s.io/apimachinery/pkg/runtime"
 	"k8s.io/apimachinery/pkg/selection"
+	"k8s.io/apimachinery/pkg/util/wait"
 	fakekubeclientset "k8s.io/client-go/kubernetes/fake"
 )
 
@@ -52,6 +54,26 @@ func (c *counter) count() int {
 	return len(c.cfg)
 }
 
+func (c *counter) eventuallyEquals(t *testing.T, want int) {
+	got := 0
+
+	err := wait.Poll(
+		// interval
+		100*time.Millisecond,
+
+		// timeout
+		5*time.Second,
+		func() (done bool, err error) {
+			got = c.count()
+			return got == want, nil
+		},
+	)
+
+	if err != nil {
+		t.Errorf("%v.count = %d, want %d", c.name, got, want)
+	}
+}
+
 func TestInformedWatcher(t *testing.T) {
 	fooCM := &corev1.ConfigMap{
 		ObjectMeta: metav1.ObjectMeta{
@@ -83,12 +105,10 @@ func TestInformedWatcher(t *testing.T) {
 		t.Fatal("cm.Start() =", err)
 	}
 
-	// When Start returns the callbacks should have been called with the
+	// When Start returns the callbacks will eventually be called with the
 	// version of the objects that is available.
-	for _, obj := range []*counter{foo1, foo2, bar} {
-		if got, want := obj.count(), 1; got != want {
-			t.Errorf("%v.count = %d, want %d", obj.name, got, want)
-		}
+	for _, count := range []*counter{foo1, foo2, bar} {
+		count.eventuallyEquals(t, 1)
 	}
 
 	// After a "foo" event, the "foo" watchers should have 2,
diff --git a/webhook/psbinding/index_test.go b/webhook/psbinding/index_test.go
index 6c8e3b812..010e31a42 100644
--- a/webhook/psbinding/index_test.go
+++ b/webhook/psbinding/index_test.go
@@ -34,9 +34,6 @@ func TestExact(t *testing.T) {
 			Namespace: "blah",
 			Name:      "asdf",
 		},
-		Spec: TestBindableSpec{
-			Foo: "bar",
-		},
 	}
 
 	gvk := want.GetGroupVersionKind()
@@ -47,19 +44,18 @@ func TestExact(t *testing.T) {
 		Name:      want.GetName(),
 	}
 
-	// Before we Add something, we shouldn't be able to Get anything.
-	if got, ok := em.Get(key); ok {
-		t.Errorf("Get(%+v) = %v, %v; wanted nil, false", key, got, ok)
+	// Before we add something, we shouldn't be able to get anything.
+	if got := em.get(key); len(got) != 0 {
+		t.Errorf("Get(%+v) = %v; wanted empty list", key, got)
 	}
 
-	// Now Add it.
-	em.Add(key, want)
+	// Now add it.
+	em.add(key, want)
 
-	// After we Add something, we should be able to Get it.
-	if got, ok := em.Get(key); !ok {
-		t.Errorf("Get(%+v) = %v, %v; wanted b, true", key, want, ok)
-	} else if !cmp.Equal(got, want) {
-		t.Error("Get (-want, +got):", cmp.Diff(want, got))
+	// After we add something, we should be able to get it.
+	wanted := []Bindable{want}
+	if got := em.get(key); !cmp.Equal(got, wanted) {
+		t.Error("Get (-want, +got):", cmp.Diff(wanted, got))
 	}
 
 	otherKey := exactKey{
@@ -69,9 +65,24 @@ func TestExact(t *testing.T) {
 		Name:      "bar",
 	}
 
-	// After we Add something, we still shouldn't return things for other keys.
-	if got, ok := em.Get(otherKey); ok {
-		t.Errorf("Get(%+v) = %v, %v; wanted nil, false", key, got, ok)
+	// After we add something, we still shouldn't return things for other keys.
+	if got := em.get(otherKey); len(got) != 0 {
+		t.Errorf("Get(%+v) = %v; wanted empty list", key, got)
+	}
+
+	// Add another Binding with the same coordinates.
+	alsoWant := &TestBindable{
+		ObjectMeta: metav1.ObjectMeta{
+			Namespace: "blah",
+			Name:      "asdf",
+		},
+	}
+	em.add(key, want)
+
+	// We should now get both Bindings.
+	wanted = []Bindable{want, alsoWant}
+	if got := em.get(key); !cmp.Equal(got, wanted) {
+		t.Error("Get (-want, +got):", cmp.Diff(wanted, got))
 	}
 }
 
@@ -85,9 +96,6 @@ func TestInexact(t *testing.T) {
 				"baz": "blah",
 			},
 		},
-		Spec: TestBindableSpec{
-			Foo: "bar",
-		},
 	}
 	ls := labels.Set(want.Labels)
 
@@ -100,8 +108,8 @@ func TestInexact(t *testing.T) {
 
 	t.Run("empty matcher doesn't match", func(t *testing.T) {
 		im := make(inexactMatcher, 1)
-		if got, ok := im.Get(key, ls); ok {
-			t.Errorf("Get(%+v) = %v, %v; wanted nil, false", key, got, ok)
+		if got := im.get(key, ls); len(got) != 0 {
+			t.Errorf("Get(%+v) = %v; wanted empty list", key, got)
 		}
 	})
 
@@ -111,13 +119,12 @@ func TestInexact(t *testing.T) {
 		// Use exactly the labels from the resource.
 		selector := ls.AsSelector()
 
-		im.Add(key, selector, want)
+		im.add(key, selector, want)
 
 		// With an appropriate selector, we match and get the binding.
-		if got, ok := im.Get(key, ls); !ok {
-			t.Errorf("Get(%+v) = %v, %v; wanted b, true", key, want, ok)
-		} else if !cmp.Equal(got, want) {
-			t.Error("Get (-want, +got):", cmp.Diff(want, got))
+		wanted := []Bindable{want}
+		if got := im.get(key, ls); !cmp.Equal(got, wanted) {
+			t.Error("Get (-want, +got):", cmp.Diff(wanted, got))
 		}
 	})
 
@@ -127,13 +134,12 @@ func TestInexact(t *testing.T) {
 		// Match everything.
 		selector := labels.Everything()
 
-		im.Add(key, selector, want)
+		im.add(key, selector, want)
 
 		// With an appropriate selector, we match and get the binding.
-		if got, ok := im.Get(key, ls); !ok {
-			t.Errorf("Get(%+v) = %v, %v; wanted b, true", key, want, ok)
-		} else if !cmp.Equal(got, want) {
-			t.Error("Get (-want, +got):", cmp.Diff(want, got))
+		wanted := []Bindable{want}
+		if got := im.get(key, ls); !cmp.Equal(got, wanted) {
+			t.Error("Get (-want, +got):", cmp.Diff(wanted, got))
 		}
 	})
 
@@ -143,10 +149,10 @@ func TestInexact(t *testing.T) {
 		// Match nothing.
 		selector := labels.Nothing()
 
-		im.Add(key, selector, want)
+		im.add(key, selector, want)
 
-		if got, ok := im.Get(key, ls); ok {
-			t.Errorf("Get(%+v) = %v, %v; wanted nil, false", key, got, ok)
+		if got := im.get(key, ls); len(got) != 0 {
+			t.Errorf("Get(%+v) = %v; wanted empty list", key, got)
 		}
 	})
 
@@ -158,13 +164,12 @@ func TestInexact(t *testing.T) {
 			"foo": "bar",
 		}).AsSelector()
 
-		im.Add(key, selector, want)
+		im.add(key, selector, want)
 
 		// With an appropriate selector, we match and get the binding.
-		if got, ok := im.Get(key, ls); !ok {
-			t.Errorf("Get(%+v) = %v, %v; wanted b, true", key, want, ok)
-		} else if !cmp.Equal(got, want) {
-			t.Error("Get (-want, +got):", cmp.Diff(want, got))
+		wanted := []Bindable{want}
+		if got := im.get(key, ls); !cmp.Equal(got, wanted) {
+			t.Error("Get (-want, +got):", cmp.Diff(wanted, got))
 		}
 	})
 
@@ -177,11 +182,11 @@ func TestInexact(t *testing.T) {
 			"not": "found",
 		}).AsSelector()
 
-		im.Add(key, selector, want)
+		im.add(key, selector, want)
 
 		// We shouldn't match because the second labels shouldn't match.
-		if got, ok := im.Get(key, ls); ok {
-			t.Errorf("Get(%+v) = %v, %v; wanted nil, false", key, got, ok)
+		if got := im.get(key, ls); len(got) != 0 {
+			t.Errorf("Get(%+v) = %v; wanted empty list", key, got)
 		}
 	})
 
@@ -191,14 +196,184 @@ func TestInexact(t *testing.T) {
 		// Use exactly the labels from the resource.
 		selector := ls.AsSelector()
 
-		im.Add(key, selector, want)
+		im.add(key, selector, want)
 
 		otherKey := key
 		otherKey.Namespace = "another"
 
 		// We shouldn't match because the second labels shouldn't match.
-		if got, ok := im.Get(otherKey, ls); ok {
-			t.Errorf("Get(%+v) = %v, %v; wanted nil, false", key, got, ok)
+		if got := im.get(otherKey, ls); len(got) != 0 {
+			t.Errorf("Get(%+v) = %v; wanted empty list", key, got)
+		}
+	})
+
+	t.Run("multiple Bindings match", func(t *testing.T) {
+		alsoWant := &TestBindable{
+			ObjectMeta: metav1.ObjectMeta{
+				Namespace: "blah",
+				Name:      "asdf",
+				Labels: map[string]string{
+					"foo": "bar",
+					"baz": "blah",
+				},
+			},
+		}
+
+		im := make(inexactMatcher, 1)
+
+		// Use a subset of the resources labels.
+		selector := labels.Set(map[string]string{
+			"foo": "bar",
+		}).AsSelector()
+
+		im.add(key, selector, want)
+		im.add(key, selector, alsoWant)
+
+		// With an appropriate selector, we match and get both bindings.
+		wanted := []Bindable{want, alsoWant}
+		if got := im.get(key, ls); !cmp.Equal(got, wanted) {
+			t.Error("Get (-want, +got):", cmp.Diff(wanted, got))
+		}
+	})
+}
+
+func TestIndex(t *testing.T) {
+	wantExact1 := &TestBindable{
+		ObjectMeta: metav1.ObjectMeta{
+			Namespace: "a",
+			Name:      "b",
+			Labels: map[string]string{
+				"colour": "red",
+			},
+		},
+	}
+
+	wantExact2 := &TestBindable{
+		ObjectMeta: metav1.ObjectMeta{
+			Namespace: "a",
+			Name:      "b",
+			Labels: map[string]string{
+				"colour": "blue",
+			},
+		},
+	}
+
+	wantInexact1 := &TestBindable{
+		ObjectMeta: metav1.ObjectMeta{
+			Namespace: "a",
+			Name:      "b",
+			Labels: map[string]string{
+				"colour": "red",
+			},
+		},
+	}
+
+	wantInexact2 := &TestBindable{
+		ObjectMeta: metav1.ObjectMeta{
+			Namespace: "a",
+			Name:      "b",
+			Labels: map[string]string{
+				"colour": "blue",
+			},
+		},
+	}
+
+	gvk := wantExact1.GetGroupVersionKind()
+	eKey := exactKey{
+		Group:     gvk.Group,
+		Kind:      gvk.Kind,
+		Namespace: wantExact1.GetNamespace(),
+		Name:      wantExact1.GetName(),
+	}
+	iKey := inexactKey{
+		Group:     gvk.Group,
+		Kind:      gvk.Kind,
+		Namespace: wantExact1.GetNamespace(),
+	}
+	redLabels := labels.Set(wantInexact1.Labels)
+	redSelector := redLabels.AsSelector()
+	blueLabels := labels.Set(wantInexact2.Labels)
+	blueSelector := blueLabels.AsSelector()
+	none := make(labels.Set)
+	allSelector := none.AsSelector()
+
+	t.Run("single exact match is found", func(t *testing.T) {
+		var index index
+		newIndexBuilder().
+			associate(eKey, wantExact1).
+			build(&index)
+
+		wanted := []Bindable{wantExact1}
+		if got := index.lookUp(eKey, none); !cmp.Equal(got, wanted) {
+			t.Error("Get (-want, +got):", cmp.Diff(wanted, got))
+		}
+	})
+
+	t.Run("single inexact match is found", func(t *testing.T) {
+		var index index
+		newIndexBuilder().
+			associateSelection(iKey, redSelector, wantInexact1).
+			build(&index)
+
+		wanted := []Bindable{wantInexact1}
+		if got := index.lookUp(eKey, redLabels); !cmp.Equal(got, wanted) {
+			t.Error("Get (-want, +got):", cmp.Diff(wanted, got))
+		}
+	})
+
+	t.Run("multiple exact matches are found", func(t *testing.T) {
+		var index index
+		newIndexBuilder().
+			associate(eKey, wantExact1).
+			associate(eKey, wantExact2).
+			build(&index)
+
+		wanted := []Bindable{wantExact1, wantExact2}
+		if got := index.lookUp(eKey, none); !cmp.Equal(got, wanted) {
+			t.Error("Get (-want, +got):", cmp.Diff(wanted, got))
+		}
+	})
+
+	t.Run("multiple inexact matches are found", func(t *testing.T) {
+		var index index
+		newIndexBuilder().
+			associateSelection(iKey, allSelector, wantInexact1).
+			associateSelection(iKey, allSelector, wantInexact2).
+			build(&index)
+
+		wanted := []Bindable{wantInexact1, wantInexact2}
+		if got := index.lookUp(eKey, redLabels); !cmp.Equal(got, wanted) {
+			t.Error("Get (-want, +got):", cmp.Diff(wanted, got))
+		}
+	})
+
+	t.Run("multiple exact and inexact matches are found", func(t *testing.T) {
+		var index index
+		newIndexBuilder().
+			associate(eKey, wantExact1).
+			associate(eKey, wantExact2).
+			associateSelection(iKey, allSelector, wantInexact1).
+			associateSelection(iKey, allSelector, wantInexact2).
+			build(&index)
+
+		wanted := []Bindable{wantExact1, wantExact2, wantInexact1, wantInexact2}
+		if got := index.lookUp(eKey, none); !cmp.Equal(got, wanted) {
+			t.Error("Get (-want, +got):", cmp.Diff(wanted, got))
+		}
+	})
+
+	t.Run("the correct exact and inexact matches are found", func(t *testing.T) {
+		var index index
+		newIndexBuilder().
+			associate(eKey, wantExact1).
+			associate(eKey, wantExact2).
+			associateSelection(iKey, redSelector, wantInexact1).
+			associateSelection(iKey, blueSelector, wantInexact2).
+			build(&index)
+
+		wanted := []Bindable{wantExact1, wantExact2, wantInexact1}
+		if got := index.lookUp(eKey, redLabels); !cmp.Equal(got, wanted) {
+			t.Error("Get (-want, +got):", cmp.Diff(wanted, got))
 		}
 	})
 }