/*
 * Copyright 2021 gRPC authors.
 *
 * 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 rbac

import (
	"errors"
	"fmt"
	"net"
	"net/netip"

	v3corepb "github.com/envoyproxy/go-control-plane/envoy/config/core/v3"
	v3rbacpb "github.com/envoyproxy/go-control-plane/envoy/config/rbac/v3"
	v3route_componentspb "github.com/envoyproxy/go-control-plane/envoy/config/route/v3"
	v3matcherpb "github.com/envoyproxy/go-control-plane/envoy/type/matcher/v3"
	internalmatcher "google.golang.org/grpc/internal/xds/matcher"
)

// matcher is an interface that takes data about incoming RPC's and returns
// whether it matches with whatever matcher implements this interface.
type matcher interface {
	match(data *rpcData) bool
}

// policyMatcher helps determine whether an incoming RPC call matches a policy.
// A policy is a logical role (e.g. Service Admin), which is comprised of
// permissions and principals. A principal is an identity (or identities) for a
// downstream subject which are assigned the policy (role), and a permission is
// an action(s) that a principal(s) can take. A policy matches if both a
// permission and a principal match, which will be determined by the child or
// permissions and principal matchers. policyMatcher implements the matcher
// interface.
type policyMatcher struct {
	permissions *orMatcher
	principals  *orMatcher
}

func newPolicyMatcher(policy *v3rbacpb.Policy) (*policyMatcher, error) {
	permissions, err := matchersFromPermissions(policy.Permissions)
	if err != nil {
		return nil, err
	}
	principals, err := matchersFromPrincipals(policy.Principals)
	if err != nil {
		return nil, err
	}
	return &policyMatcher{
		permissions: &orMatcher{matchers: permissions},
		principals:  &orMatcher{matchers: principals},
	}, nil
}

func (pm *policyMatcher) match(data *rpcData) bool {
	// A policy matches if and only if at least one of its permissions match the
	// action taking place AND at least one if its principals match the
	// downstream peer.
	return pm.permissions.match(data) && pm.principals.match(data)
}

// matchersFromPermissions takes a list of permissions (can also be
// a single permission, e.g. from a not matcher which is logically !permission)
// and returns a list of matchers which correspond to that permission. This will
// be called in many instances throughout the initial construction of the RBAC
// engine from the AND and OR matchers and also from the NOT matcher.
func matchersFromPermissions(permissions []*v3rbacpb.Permission) ([]matcher, error) {
	var matchers []matcher
	for _, permission := range permissions {
		switch p := permission.GetRule().(type) {
		case *v3rbacpb.Permission_AndRules:
			mList, err := matchersFromPermissions(permission.GetAndRules().Rules)
			if err != nil {
				return nil, err
			}
			matchers = append(matchers, &andMatcher{matchers: mList})
		case *v3rbacpb.Permission_OrRules:
			mList, err := matchersFromPermissions(permission.GetOrRules().Rules)
			if err != nil {
				return nil, err
			}
			matchers = append(matchers, &orMatcher{matchers: mList})
		case *v3rbacpb.Permission_Any:
			matchers = append(matchers, &alwaysMatcher{})
		case *v3rbacpb.Permission_Header:
			m, err := newHeaderMatcher(permission.GetHeader())
			if err != nil {
				return nil, err
			}
			matchers = append(matchers, m)
		case *v3rbacpb.Permission_UrlPath:
			m, err := newURLPathMatcher(permission.GetUrlPath())
			if err != nil {
				return nil, err
			}
			matchers = append(matchers, m)
		case *v3rbacpb.Permission_DestinationIp:
			// Due to this being on server side, the destination IP is the local
			// IP.
			m, err := newLocalIPMatcher(permission.GetDestinationIp())
			if err != nil {
				return nil, err
			}
			matchers = append(matchers, m)
		case *v3rbacpb.Permission_DestinationPort:
			matchers = append(matchers, newPortMatcher(permission.GetDestinationPort()))
		case *v3rbacpb.Permission_NotRule:
			mList, err := matchersFromPermissions([]*v3rbacpb.Permission{{Rule: permission.GetNotRule().Rule}})
			if err != nil {
				return nil, err
			}
			if len(mList) != 1 {
				return nil, fmt.Errorf("NotRule must contain exactly one rule")
			}
			matchers = append(matchers, &notMatcher{matcherToNot: mList[0]})
		case *v3rbacpb.Permission_Metadata:
			if permission.GetMetadata().GetInvert() {
				matchers = append(matchers, &alwaysMatcher{})
			} else {
				matchers = append(matchers, &neverMatcher{})
			}
		case *v3rbacpb.Permission_RequestedServerName:
			m, err := newRequestedServerNameMatcher(permission.GetRequestedServerName())
			if err != nil {
				return nil, err
			}
			matchers = append(matchers, m)
		default:
			return nil, fmt.Errorf("unsupported permission rule type: %T", p)
		}
	}
	return matchers, nil
}

func matchersFromPrincipals(principals []*v3rbacpb.Principal) ([]matcher, error) {
	var matchers []matcher
	for _, principal := range principals {
		switch p := principal.GetIdentifier().(type) {
		case *v3rbacpb.Principal_AndIds:
			mList, err := matchersFromPrincipals(principal.GetAndIds().Ids)
			if err != nil {
				return nil, err
			}
			matchers = append(matchers, &andMatcher{matchers: mList})
		case *v3rbacpb.Principal_OrIds:
			mList, err := matchersFromPrincipals(principal.GetOrIds().Ids)
			if err != nil {
				return nil, err
			}
			matchers = append(matchers, &orMatcher{matchers: mList})
		case *v3rbacpb.Principal_Any:
			matchers = append(matchers, &alwaysMatcher{})
		case *v3rbacpb.Principal_Authenticated_:
			authenticatedMatcher, err := newAuthenticatedMatcher(principal.GetAuthenticated())
			if err != nil {
				return nil, err
			}
			matchers = append(matchers, authenticatedMatcher)
		case *v3rbacpb.Principal_DirectRemoteIp:
			m, err := newRemoteIPMatcher(principal.GetDirectRemoteIp())
			if err != nil {
				return nil, err
			}
			matchers = append(matchers, m)
		case *v3rbacpb.Principal_Header:
			// Do we need an error here?
			m, err := newHeaderMatcher(principal.GetHeader())
			if err != nil {
				return nil, err
			}
			matchers = append(matchers, m)
		case *v3rbacpb.Principal_UrlPath:
			m, err := newURLPathMatcher(principal.GetUrlPath())
			if err != nil {
				return nil, err
			}
			matchers = append(matchers, m)
		case *v3rbacpb.Principal_Metadata:
			if principal.GetMetadata().GetInvert() {
				matchers = append(matchers, &alwaysMatcher{})
			} else {
				matchers = append(matchers, &neverMatcher{})
			}
		case *v3rbacpb.Principal_NotId:
			mList, err := matchersFromPrincipals([]*v3rbacpb.Principal{{Identifier: principal.GetNotId().Identifier}})
			if err != nil {
				return nil, err
			}
			if len(mList) != 1 {
				return nil, fmt.Errorf("NotId must contain exactly one identifier")
			}
			matchers = append(matchers, &notMatcher{matcherToNot: mList[0]})
		case *v3rbacpb.Principal_SourceIp:
			// The source ip principal identifier is deprecated, but gRPC RBAC
			// treats it as equivalent to direct_remote_ip as per A41.
			m, err := newRemoteIPMatcher(principal.GetSourceIp())
			if err != nil {
				return nil, err
			}
			matchers = append(matchers, m)
		case *v3rbacpb.Principal_RemoteIp:
			// RBAC in gRPC treats direct_remote_ip and remote_ip as logically
			// equivalent, as per A41.
			m, err := newRemoteIPMatcher(principal.GetRemoteIp())
			if err != nil {
				return nil, err
			}
			matchers = append(matchers, m)
		default:
			return nil, fmt.Errorf("unsupported principal identifier type: %T", p)
		}
	}
	return matchers, nil
}

// orMatcher is a matcher where it successfully matches if one of it's
// children successfully match. It also logically represents a principal or
// permission, but can also be it's own entity further down the tree of
// matchers. orMatcher implements the matcher interface.
type orMatcher struct {
	matchers []matcher
}

func (om *orMatcher) match(data *rpcData) bool {
	// Range through child matchers and pass in data about incoming RPC, and
	// only one child matcher has to match to be logically successful.
	for _, m := range om.matchers {
		if m.match(data) {
			return true
		}
	}
	return false
}

// andMatcher is a matcher that is successful if every child matcher
// matches. andMatcher implements the matcher interface.
type andMatcher struct {
	matchers []matcher
}

func (am *andMatcher) match(data *rpcData) bool {
	for _, m := range am.matchers {
		if !m.match(data) {
			return false
		}
	}
	return true
}

// alwaysMatcher is a matcher that will always match. This logically
// represents an any rule for a permission or a principal. alwaysMatcher
// implements the matcher interface.
type alwaysMatcher struct {
}

func (am *alwaysMatcher) match(*rpcData) bool {
	return true
}

// neverMatcher is a matcher that will never match. This logically represents a
// permission or principal that is unsupported in gRPC. neverMatcher implements
// the matcher interface.
type neverMatcher struct {
}

func (nm *neverMatcher) match(*rpcData) bool {
	return false
}

// notMatcher is a matcher that nots an underlying matcher. notMatcher
// implements the matcher interface.
type notMatcher struct {
	matcherToNot matcher
}

func (nm *notMatcher) match(data *rpcData) bool {
	return !nm.matcherToNot.match(data)
}

// headerMatcher is a matcher that matches on incoming HTTP Headers present
// in the incoming RPC. headerMatcher implements the matcher interface.
type headerMatcher struct {
	matcher internalmatcher.HeaderMatcher
}

func newHeaderMatcher(headerMatcherConfig *v3route_componentspb.HeaderMatcher) (*headerMatcher, error) {
	var m internalmatcher.HeaderMatcher
	switch headerMatcherConfig.HeaderMatchSpecifier.(type) {
	case *v3route_componentspb.HeaderMatcher_ExactMatch:
		m = internalmatcher.NewHeaderExactMatcher(headerMatcherConfig.Name, headerMatcherConfig.GetExactMatch(), headerMatcherConfig.InvertMatch)
	case *v3route_componentspb.HeaderMatcher_SafeRegexMatch:
		regex, err := internalmatcher.CompileSafeRegex(headerMatcherConfig.GetSafeRegexMatch().GetRegex())
		if err != nil {
			return nil, err
		}
		m = internalmatcher.NewHeaderRegexMatcher(headerMatcherConfig.Name, regex, headerMatcherConfig.InvertMatch)
	case *v3route_componentspb.HeaderMatcher_RangeMatch:
		m = internalmatcher.NewHeaderRangeMatcher(headerMatcherConfig.Name, headerMatcherConfig.GetRangeMatch().Start, headerMatcherConfig.GetRangeMatch().End, headerMatcherConfig.InvertMatch)
	case *v3route_componentspb.HeaderMatcher_PresentMatch:
		m = internalmatcher.NewHeaderPresentMatcher(headerMatcherConfig.Name, headerMatcherConfig.GetPresentMatch(), headerMatcherConfig.InvertMatch)
	case *v3route_componentspb.HeaderMatcher_PrefixMatch:
		m = internalmatcher.NewHeaderPrefixMatcher(headerMatcherConfig.Name, headerMatcherConfig.GetPrefixMatch(), headerMatcherConfig.InvertMatch)
	case *v3route_componentspb.HeaderMatcher_SuffixMatch:
		m = internalmatcher.NewHeaderSuffixMatcher(headerMatcherConfig.Name, headerMatcherConfig.GetSuffixMatch(), headerMatcherConfig.InvertMatch)
	case *v3route_componentspb.HeaderMatcher_ContainsMatch:
		m = internalmatcher.NewHeaderContainsMatcher(headerMatcherConfig.Name, headerMatcherConfig.GetContainsMatch(), headerMatcherConfig.InvertMatch)
	case *v3route_componentspb.HeaderMatcher_StringMatch:
		sm, err := internalmatcher.StringMatcherFromProto(headerMatcherConfig.GetStringMatch())
		if err != nil {
			return nil, fmt.Errorf("invalid string matcher %+v: %v", headerMatcherConfig.GetStringMatch(), err)
		}
		m = internalmatcher.NewHeaderStringMatcher(headerMatcherConfig.Name, sm, headerMatcherConfig.InvertMatch)
	default:
		return nil, errors.New("unknown header matcher type")
	}
	return &headerMatcher{matcher: m}, nil
}

func (hm *headerMatcher) match(data *rpcData) bool {
	return hm.matcher.Match(data.md)
}

// urlPathMatcher matches on the URL Path of the incoming RPC. In gRPC, this
// logically maps to the full method name the RPC is calling on the server side.
// urlPathMatcher implements the matcher interface.
type urlPathMatcher struct {
	stringMatcher internalmatcher.StringMatcher
}

func newURLPathMatcher(pathMatcher *v3matcherpb.PathMatcher) (*urlPathMatcher, error) {
	stringMatcher, err := internalmatcher.StringMatcherFromProto(pathMatcher.GetPath())
	if err != nil {
		return nil, err
	}
	return &urlPathMatcher{stringMatcher: stringMatcher}, nil
}

func (upm *urlPathMatcher) match(data *rpcData) bool {
	return upm.stringMatcher.Match(data.fullMethod)
}

// remoteIPMatcher and localIPMatcher both are matchers that match against
// a CIDR Range. Two different matchers are needed as the remote and destination
// ip addresses come from different parts of the data about incoming RPC's
// passed in. Matching a CIDR Range means to determine whether the IP Address
// falls within the CIDR Range or not. They both implement the matcher
// interface.
type remoteIPMatcher struct {
	// ipNet represents the CidrRange that this matcher was configured with.
	// This is what will remote and destination IP's will be matched against.
	ipNet netip.Prefix
}

func newRemoteIPMatcher(cidrRange *v3corepb.CidrRange) (*remoteIPMatcher, error) {
	// Convert configuration to a cidrRangeString, as Go standard library has
	// methods that parse cidr string.
	cidrRangeString := fmt.Sprintf("%s/%d", cidrRange.GetAddressPrefix(), cidrRange.GetPrefixLen().GetValue())
	ipNet, err := netip.ParsePrefix(cidrRangeString)
	if err != nil {
		return nil, err
	}
	return &remoteIPMatcher{ipNet: ipNet.Masked()}, nil
}

func (sim *remoteIPMatcher) match(data *rpcData) bool {
	host, _, err := net.SplitHostPort(data.peerInfo.Addr.String())
	if err != nil {
		// Fallback for addresses without a port.
		host = data.peerInfo.Addr.String()
	}
	ip, err := netip.ParseAddr(host)
	if err != nil {
		return false
	}
	return sim.ipNet.Contains(ip)
}

type localIPMatcher struct {
	ipNet netip.Prefix
}

func newLocalIPMatcher(cidrRange *v3corepb.CidrRange) (*localIPMatcher, error) {
	cidrRangeString := fmt.Sprintf("%s/%d", cidrRange.GetAddressPrefix(), cidrRange.GetPrefixLen().GetValue())
	ipNet, err := netip.ParsePrefix(cidrRangeString)
	if err != nil {
		return nil, err
	}
	return &localIPMatcher{ipNet: ipNet.Masked()}, nil
}

func (dim *localIPMatcher) match(data *rpcData) bool {
	host, _, err := net.SplitHostPort(data.localAddr.String())
	if err != nil {
		// Fallback for addresses without a port.
		host = data.localAddr.String()
	}
	ip, err := netip.ParseAddr(host)
	if err != nil {
		return false
	}
	return dim.ipNet.Contains(ip)
}

// portMatcher matches on whether the destination port of the RPC matches the
// destination port this matcher was instantiated with. portMatcher
// implements the matcher interface.
type portMatcher struct {
	destinationPort uint32
}

func newPortMatcher(destinationPort uint32) *portMatcher {
	return &portMatcher{destinationPort: destinationPort}
}

func (pm *portMatcher) match(data *rpcData) bool {
	return data.destinationPort == pm.destinationPort
}

// requestedServerNameMatcher matches on if the given string matcher matches
// on "", as per A41-xds-rbac.md. requestedServerNameMatcher implements
// the matcher interface.
type requestedServerNameMatcher struct {
	stringMatcher internalmatcher.StringMatcher
}

func newRequestedServerNameMatcher(stringMatcherProto *v3matcherpb.StringMatcher) (*requestedServerNameMatcher, error) {
	stringMatcher, err := internalmatcher.StringMatcherFromProto(stringMatcherProto)
	if err != nil {
		return nil, err
	}
	return &requestedServerNameMatcher{stringMatcher: stringMatcher}, nil
}

func (r *requestedServerNameMatcher) match(*rpcData) bool {
	return r.stringMatcher.Match("")
}

// authenticatedMatcher matches on the name of the Principal. If set, the URI
// SAN or DNS SAN in that order is used from the certificate, otherwise the
// subject field is used. If unset, it applies to any user that is
// authenticated. authenticatedMatcher implements the matcher interface.
type authenticatedMatcher struct {
	stringMatcher *internalmatcher.StringMatcher
}

func newAuthenticatedMatcher(authenticatedMatcherConfig *v3rbacpb.Principal_Authenticated) (*authenticatedMatcher, error) {
	// Represents this line in the RBAC documentation = "If unset, it applies to
	// any user that is authenticated" (see package-level comments).
	if authenticatedMatcherConfig.PrincipalName == nil {
		return &authenticatedMatcher{}, nil
	}
	stringMatcher, err := internalmatcher.StringMatcherFromProto(authenticatedMatcherConfig.PrincipalName)
	if err != nil {
		return nil, err
	}
	return &authenticatedMatcher{stringMatcher: &stringMatcher}, nil
}

func (am *authenticatedMatcher) match(data *rpcData) bool {
	if data.authType != "tls" {
		// Connection is not authenticated.
		return false
	}
	if am.stringMatcher == nil {
		// Allows any authenticated user.
		return true
	}
	// "If there is no client certificate (thus no SAN nor Subject), check if ""
	// (empty string) matches. If it matches, the principal_name is said to
	// match" - A41
	if len(data.certs) == 0 {
		return am.stringMatcher.Match("")
	}
	cert := data.certs[0]
	// Use the first non-empty identity source in priority order:
	// URI SANs, then DNS SANs, then Subject.
	if len(cert.URIs) > 0 {
		for _, uriSAN := range cert.URIs {
			if am.stringMatcher.Match(uriSAN.String()) {
				return true
			}
		}
		return false
	}
	if len(cert.DNSNames) > 0 {
		for _, dnsSAN := range cert.DNSNames {
			if am.stringMatcher.Match(dnsSAN) {
				return true
			}
		}
		return false
	}
	return am.stringMatcher.Match(cert.Subject.String())
}
