Repository: googleforgames/open-match
Pull request #513 (2019-06-11 02:08:55)

Add filter package
This package will be useful for a simple definition of how filters work, as well as a way to process tickets without relying on indexes.  This will allow other filter types (eg, strings) to be added without a redis implementation.  See package documentation for some more details.

I plan on replacing the current redis indexing with a "all tickets" index to remove the edge cases it gets wrong that we don't want to spend time fixing for v0.6.  Instead this package will be responsible for filtering which tickets to return.  This also removes the index configuration problem from v0.6. Then for v0.7, once the indexing and database solutions are chosen, we can go back to implementing the correct way to be indexing tickets.

Also included are test cases, separated in their own definition.  These test cases should be used in the future for end to end tests, and for tests on indexes.  This will help ensure that the system as a whole maintains the behavior specified here.


Patch:
diff --git a/internal/filter/filter.go b/internal/filter/filter.go
new file mode 100644
index 00000000..eb1a181e
--- /dev/null
+++ b/internal/filter/filter.go
@@ -0,0 +1,66 @@
+// Copyright 2019 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// 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
+// limitations under the License.
+
+// Package filter defines which tickets pass which filters.  Other implementations which help
+// filter tickets (eg, a range index lookup) must conform to the same set of tickets being within
+// the filter as here.
+package filter
+
+import (
+	structpb "github.com/golang/protobuf/ptypes/struct"
+	"open-match.dev/open-match/internal/pb"
+)
+
+// Filter returns all of the passed tickets which are included by all the passed filters.
+func Filter(tickets []*pb.Ticket, filters []*pb.Filter) []*pb.Ticket {
+	var result []*pb.Ticket
+
+	for _, t := range tickets {
+		if InFilters(t, filters) {
+			result = append(result, t)
+		}
+	}
+
+	return result
+}
+
+// InFilters returns if the given ticket is included in all of the passed filters.
+func InFilters(ticket *pb.Ticket, filters []*pb.Filter) bool {
+	for _, f := range filters {
+		if !InFilter(ticket, f) {
+			return false
+		}
+	}
+	return true
+}
+
+// InFilter returns if the given ticket is included in the given filter.
+func InFilter(ticket *pb.Ticket, filter *pb.Filter) bool {
+	if ticket.GetProperties().GetFields() == nil {
+		return false
+	}
+
+	v, ok := ticket.Properties.Fields[filter.Attribute]
+	if !ok {
+		return false
+	}
+
+	switch v.Kind.(type) {
+	case *structpb.Value_NumberValue:
+		nv := v.GetNumberValue()
+		return filter.Min <= nv && nv <= filter.Max
+	default:
+		return false
+	}
+}


Test patch:
diff --git a/internal/filter/filter_test.go b/internal/filter/filter_test.go
new file mode 100644
index 00000000..32553a83
--- /dev/null
+++ b/internal/filter/filter_test.go
@@ -0,0 +1,126 @@
+// Copyright 2019 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// 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
+// limitations under the License.
+
+package filter
+
+import (
+	"testing"
+
+	structpb "github.com/golang/protobuf/ptypes/struct"
+	"open-match.dev/open-match/internal/filter/testcases"
+	"open-match.dev/open-match/internal/pb"
+)
+
+// Only test Filter and InFilters for general use cases, not specific scenearios
+// on a filter/property interaction.  Filter and InFilters defer to InFilter for
+// all specific Filter and Ticket Property interaction.
+
+func TestFilter(t *testing.T) {
+	tickets := []*pb.Ticket{
+		&pb.Ticket{
+			Id: "good",
+			Properties: &structpb.Struct{
+				Fields: map[string]*structpb.Value{
+					"field1": {Kind: &structpb.Value_NumberValue{NumberValue: 5}},
+					"field2": {Kind: &structpb.Value_NumberValue{NumberValue: 5}},
+				},
+			},
+		},
+
+		&pb.Ticket{
+			Id: "first_bad",
+			Properties: &structpb.Struct{
+				Fields: map[string]*structpb.Value{
+					"field1": {Kind: &structpb.Value_NumberValue{NumberValue: -5}},
+					"field2": {Kind: &structpb.Value_NumberValue{NumberValue: 5}},
+				},
+			},
+		},
+
+		&pb.Ticket{
+			Id: "second_bad",
+			Properties: &structpb.Struct{
+				Fields: map[string]*structpb.Value{
+					"field1": {Kind: &structpb.Value_NumberValue{NumberValue: 5}},
+					"field2": {Kind: &structpb.Value_NumberValue{NumberValue: -5}},
+				},
+			},
+		},
+
+		&pb.Ticket{
+			Id: "both_bad",
+			Properties: &structpb.Struct{
+				Fields: map[string]*structpb.Value{
+					"field1": {Kind: &structpb.Value_NumberValue{NumberValue: -5}},
+					"field2": {Kind: &structpb.Value_NumberValue{NumberValue: -5}},
+				},
+			},
+		},
+	}
+
+	filters := []*pb.Filter{
+		{
+			Attribute: "field1",
+			Min:       0,
+			Max:       10,
+		},
+		{
+			Attribute: "field2",
+			Min:       0,
+			Max:       10,
+		},
+	}
+
+	result := Filter(tickets, filters)
+
+	if len(result) != 1 {
+		t.Fatalf("Expected exactly 1 ticket to pass filters, got %d", len(result))
+	}
+
+	if result[0].Id != "good" {
+		t.Fatalf("Expected ticket id good, got %s", result[0].Id)
+	}
+}
+
+func TestInFilters(t *testing.T) {
+	ticket := &pb.Ticket{
+		Id: "good",
+	}
+
+	filters := []*pb.Filter{}
+
+	passed := InFilters(ticket, filters)
+
+	if !passed {
+		t.Fatal("No filters should allow all tickets")
+	}
+}
+
+func TestInFilter(t *testing.T) {
+	for _, tt := range testcases.IncludedTestCases() {
+		t.Run(tt.Name, func(t *testing.T) {
+			if !InFilter(tt.Ticket, tt.Filter) {
+				t.Error("Ticket should be included in filter.")
+			}
+		})
+	}
+
+	for _, tt := range testcases.ExcludedTestCases() {
+		t.Run(tt.Name, func(t *testing.T) {
+			if InFilter(tt.Ticket, tt.Filter) {
+				t.Error("Ticket should be excluded from filter.")
+			}
+		})
+	}
+}
diff --git a/internal/filter/testcases/testcases.go b/internal/filter/testcases/testcases.go
new file mode 100644
index 00000000..8ba1ff61
--- /dev/null
+++ b/internal/filter/testcases/testcases.go
@@ -0,0 +1,111 @@
+// Copyright 2019 Google LLC
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// 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
+// limitations under the License.
+
+// Package testcases contains lists of ticket filtering test cases.
+package testcases
+
+import (
+	"math"
+
+	structpb "github.com/golang/protobuf/ptypes/struct"
+	"open-match.dev/open-match/internal/pb"
+)
+
+// TestCase defines a single filtering test case to run.
+type TestCase struct {
+	Name   string
+	Ticket *pb.Ticket
+	Filter *pb.Filter
+}
+
+// IncludedTestCases returns a list of test cases where using the given filter,
+// the ticket is included in the result.
+func IncludedTestCases() []TestCase {
+	return []TestCase{
+		simpleRangeTest("simpleInRange", 5, 0, 10),
+		simpleRangeTest("exactMatch", 5, 5, 5),
+		simpleRangeTest("infinityMax", math.Inf(1), 0, math.Inf(1)),
+		simpleRangeTest("infinityMin", math.Inf(-1), math.Inf(-1), 0),
+	}
+}
+
+// ExcludedTestCases returns a list of test cases where using the given filter,
+// the ticket is NOT included in the result.
+func ExcludedTestCases() []TestCase {
+	return []TestCase{
+		{
+			"missingField",
+			&pb.Ticket{
+				Properties: &structpb.Struct{
+					Fields: map[string]*structpb.Value{},
+				},
+			},
+			&pb.Filter{
+				Attribute: "field",
+				Min:       5,
+				Max:       5,
+			},
+		},
+
+		{
+			"missingFieldsMap",
+			&pb.Ticket{
+				Properties: &structpb.Struct{
+					Fields: nil,
+				},
+			},
+			&pb.Filter{
+				Attribute: "field",
+				Min:       5,
+				Max:       5,
+			},
+		},
+
+		{
+			"missingProperties",
+			&pb.Ticket{
+				Properties: nil,
+			},
+			&pb.Filter{
+				Attribute: "field",
+				Min:       5,
+				Max:       5,
+			},
+		},
+
+		simpleRangeTest("valueTooLow", -1, 0, 10),
+		simpleRangeTest("valueTooHigh", 11, 0, 10),
+		simpleRangeTest("minIsNan", 5, math.NaN(), 10),
+		simpleRangeTest("maxIsNan", 5, 0, math.NaN()),
+		simpleRangeTest("valueIsNan", math.NaN(), 0, 10),
+	}
+}
+
+func simpleRangeTest(name string, value, min, max float64) TestCase {
+	return TestCase{
+		name,
+		&pb.Ticket{
+			Properties: &structpb.Struct{
+				Fields: map[string]*structpb.Value{
+					"field": {Kind: &structpb.Value_NumberValue{NumberValue: value}},
+				},
+			},
+		},
+		&pb.Filter{
+			Attribute: "field",
+			Min:       min,
+			Max:       max,
+		},
+	}
+}