Unified Matcher REpair

match.go

package match

import (
	xds "github.com/cncf/xds/go/xds/core/v3"
	matcher "github.com/cncf/xds/go/xds/type/matcher/v3"
	network "github.com/envoyproxy/go-control-plane/envoy/extensions/matching/common_inputs/network/v3"
	"github.com/golang/protobuf/ptypes/wrappers"
	"istio.io/istio/pilot/pkg/networking/util"
	"istio.io/pkg/log"
)

var (
	DestinationPort = &xds.TypedExtensionConfig{
		Name:        "port",
		TypedConfig: util.MessageToAny(&network.DestinationPortInput{}),
	}
	DestinationIP = &xds.TypedExtensionConfig{
		Name:        "ip",
		TypedConfig: util.MessageToAny(&network.DestinationIPInput{}),
	}
	SourceIP = &xds.TypedExtensionConfig{
		Name:        "source-ip",
		TypedConfig: util.MessageToAny(&network.SourceIPInput{}),
	}
	SNI = &xds.TypedExtensionConfig{
		Name:        "sni",
		TypedConfig: util.MessageToAny(&network.ServerNameInput{}),
	}
	ApplicationProtocolInput = &xds.TypedExtensionConfig{
		Name:        "application-protocol",
		TypedConfig: util.MessageToAny(&network.ApplicationProtocolInput{}),
	}
	TransportProtocolInput = &xds.TypedExtensionConfig{
		Name:        "transport-protocol",
		TypedConfig: util.MessageToAny(&network.TransportProtocolInput{}),
	}
)

type Mapper struct {
	*matcher.Matcher
	Map map[string]*matcher.Matcher_OnMatch
}

func newMapper(input *xds.TypedExtensionConfig) Mapper {
	m := map[string]*matcher.Matcher_OnMatch{}
	match := &matcher.Matcher{
		MatcherType: &matcher.Matcher_MatcherTree_{
			MatcherTree: &matcher.Matcher_MatcherTree{
				Input: input,
				TreeType: &matcher.Matcher_MatcherTree_ExactMatchMap{
					ExactMatchMap: &matcher.Matcher_MatcherTree_MatchMap{
						Map: m,
					},
				},
			},
		},
		OnNoMatch: nil,
	}
	return Mapper{Matcher: match, Map: m}
}

func NewDestinationIP() Mapper {
	return newMapper(DestinationIP)
}

func NewSourceIP() Mapper {
	return newMapper(SourceIP)
}

func NewDestinationPort() Mapper {
	return newMapper(DestinationPort)
}

func ToChain(name string) *matcher.Matcher_OnMatch {
	return &matcher.Matcher_OnMatch{
		OnMatch: &matcher.Matcher_OnMatch_Action{
			Action: &xds.TypedExtensionConfig{
				Name:        name,
				TypedConfig: util.MessageToAny(&wrappers.StringValue{Value: name}),
			},
		},
	}
}

func ToMatcher(match *matcher.Matcher) *matcher.Matcher_OnMatch {
	return &matcher.Matcher_OnMatch{
		OnMatch: &matcher.Matcher_OnMatch_Matcher{
			Matcher: match,
		},
	}
}

// BuildMatcher cleans the entire match tree to avoid empty maps and returns a viable top-level matcher.
// Note: this mutates the internal mappers/matchers that make up the tree.
func (m Mapper) BuildMatcher() *matcher.Matcher {
	root := m
	for len(root.Map) == 0 {
		// the top level matcher is empty; if its fallback goes to a matcher, return that
		// TODO is there a way we can just say "always go to action"?
		if fallback := root.GetOnNoMatch(); fallback != nil {
			if replacement, ok := mapperFromMatch(fallback.GetMatcher()); ok {
				root = replacement
				continue
			}
		}
		// no fallback or fallback isn't a mapper
		log.Warnf("could not repair invalid matcher; empty map at root matcher does not have a map fallback")
		return nil
	}
	q := []*matcher.Matcher_OnMatch{m.OnNoMatch}
	for _, onMatch := range root.Map {
		q = append(q, onMatch)
	}

	// fix the matchers, add child mappers OnMatch to the queue
	for len(q) > 0 {
		head := q[0]
		q = q[1:]
		q = append(q, fixEmptyOnMatchMap(head)...)
	}
	return root.Matcher
}

// if the onMatch sends to an empty mapper, make the onMatch send directly to the onNoMatch of that empty mapper
// returns mapper if it doesn't need to be fixed, or can't be fixed
func fixEmptyOnMatchMap(onMatch *matcher.Matcher_OnMatch) []*matcher.Matcher_OnMatch {
	if onMatch == nil {
		return nil
	}
	innerMatcher := onMatch.GetMatcher()
	if innerMatcher == nil {
		// this already just performs an Action
		return nil
	}
	innerMapper, ok := mapperFromMatch(innerMatcher)
	if !ok {
		// this isn't a mapper or action, not supported by this func
		return nil
	}
	if len(innerMapper.Map) > 0 {
		return innerMapper.allOnMatches()
	}

	if fallback := innerMapper.GetOnNoMatch(); fallback != nil {
		// change from: onMatch -> map (empty with fallback) to onMatch -> fallback
		// that fallback may be an empty map, so we re-queue onMatch in case it still needs fixing
		onMatch.OnMatch = fallback.OnMatch
		return []*matcher.Matcher_OnMatch{onMatch} // the inner mapper is gone
	}

	// envoy will nack this eventually
	log.Warnf("empty mapper %v with no fallback", innerMapper.Matcher)
	return innerMapper.allOnMatches()
}

func (m Mapper) allOnMatches() []*matcher.Matcher_OnMatch {
	var out []*matcher.Matcher_OnMatch
	out = append(out, m.OnNoMatch)
	if m.Map == nil {
		return out
	}
	for _, match := range m.Map {
		out = append(out, match)
	}
	return out
}

func mapperFromMatch(mmatcher *matcher.Matcher) (Mapper, bool) {
	if mmatcher == nil {
		return Mapper{}, false
	}
	switch m := mmatcher.MatcherType.(type) {
	case *matcher.Matcher_MatcherTree_:
		var mmap *matcher.Matcher_MatcherTree_MatchMap
		switch t := m.MatcherTree.TreeType.(type) {
		case *matcher.Matcher_MatcherTree_PrefixMatchMap:
			mmap = t.PrefixMatchMap
		case *matcher.Matcher_MatcherTree_ExactMatchMap:
			mmap = t.ExactMatchMap
		default:
			return Mapper{}, false
		}
		return Mapper{Matcher: mmatcher, Map: mmap.Map}, true
	}
	return Mapper{}, false
}

match_test.go

package match

import (
	matcher "github.com/cncf/xds/go/xds/type/matcher/v3"
	"github.com/google/go-cmp/cmp"
	"istio.io/istio/pkg/util/protomarshal"
	"testing"
)

func TestCleanupEmptyMaps(t *testing.T) {
	tc := []struct {
		name  string
		given func() Mapper
		want  func() *matcher.Matcher
	}{
		{
			name: "empty map at depth = 0",
			given: func() Mapper {
				// root (dest port):
				//   <no matches>
				//   fallback (dest ip):
				//     1.2.3.4: chain
				fallback := NewDestinationIP()
				fallback.Map["1.2.3.4"] = ToChain("chain")

				root := NewDestinationPort()
				root.OnNoMatch = ToMatcher(fallback.Matcher)
				return root
			},
			want: func() *matcher.Matcher {
				// root (dest ip):
				//   1.2.3.4: chain

				// fallback becomes root
				want := NewDestinationIP()
				want.Map["1.2.3.4"] = ToChain("chain")
				return want.Matcher
			},
		},
		{
			name: "empty map at depth = 1",
			given: func() Mapper {
				// root (dest port)
				//   15001:
				//     inner (dest ip):
				//       <no matches>
				//       fallback: chain
				inner := NewDestinationIP()
				inner.OnNoMatch = ToChain("chain")

				root := NewDestinationPort()
				root.Map["15001"] = ToMatcher(inner.Matcher)
				return root
			},
			want: func() *matcher.Matcher {
				// dest port
				// 15001: chain
				want := NewDestinationPort()
				want.Map["15001"] = ToChain("chain")
				return want.Matcher
			},
		},
		{
			name: "empty map at depth = 0 and 1",
			given: func() Mapper {
				// root (dest port)
				//   fallback:
				//     inner (dest ip):
				//       <no matches>
				//       fallback (src ip):
				//         1.2.3.4: chain

				inner := NewSourceIP()
				inner.Map["1.2.3.4"] = ToChain("chain")

				middle := NewDestinationIP()
				middle.OnNoMatch = ToMatcher(inner.Matcher)

				root := NewDestinationPort()
				root.OnNoMatch = ToMatcher(middle.Matcher)
				return root
			},
			want: func() *matcher.Matcher {
				// src ip
				// 1.2.3.4: chain
				want := NewSourceIP()
				want.Map["1.2.3.4"] = ToChain("chain")
				return want.Matcher
			},
		},
		{
			name: "empty map at depths = 1 and 2",
			given: func() Mapper {
				// root (dest port)
				//   15001:
				//     depth1 (SNI):
				//       fallback:
				//         depth2 (src ip):
				//           fallback: chain
				depth2 := NewDestinationIP()
				depth2.OnNoMatch = ToChain("chain")

				depth1 := newMapper(SNI)
				depth1.OnNoMatch = ToMatcher(depth2.Matcher)

				root := NewDestinationPort()
				root.Map["15001"] = ToMatcher(depth1.Matcher)
				return root
			},
			want: func() *matcher.Matcher {
				// dest port
				// 15001: chain
				want := NewDestinationPort()
				want.Map["15001"] = ToChain("chain")
				return want.Matcher
			},
		},
	}

	for _, tt := range tc {
		t.Run(tt.name, func(t *testing.T) {
			got := tt.given().BuildMatcher()
			haveJSON, _ := protomarshal.ToJSONWithIndent(got, "  ")
			wantJSON, _ := protomarshal.ToJSONWithIndent(tt.want(), "  ")

			if diff := cmp.Diff(haveJSON, wantJSON, cmp.AllowUnexported()); diff != "" {
				t.Error(haveJSON)
				t.Error(wantJSON)
				t.Error(diff)
			}
		})
	}

}