services/groups/pattern.go - release.go.v23 - Git at Google

 // Copyright 2015 The Vanadium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.

 // This is WIP to implement and test algorithms that match blessings
 // against blessing patterns that involve groups. We expect to
 // eventually migrate some of this code to v23/security/pattern.go.

 package groups

 import (
 	"errors"
 	"regexp"
 	"strings"

 	"v.io/v23/context"
 	"v.io/v23/security"
 	"v.io/v23/verror"
 )

 const (
 	GroupStart = "<grp:" // GroupStart indicates the start of a group name in a blessing pattern.
 	GroupEnd   = ">"     // GroupEnd indicates the end of a group name in a blessing pattern.
 )

 var (
 	exactMatch    = convertToSet("")
 	grpRegexp     = regexp.MustCompile(GroupStart + "[^" + GroupEnd + "]*" + GroupEnd)
 	grpStartToken = strings.TrimSuffix(GroupStart, security.ChainSeparator)
 )

 // Match matches blessing names against a pattern. It returns an empty array if
 // the presented blessing names do not match the pattern, or a set of suffixes
 // when the pattern is a prefix of the blessing names. Match approximates the
 // result if any errors are encountered during the matching process.
 //
 // Match assumes presented blessing names are valid. ctx is used to make any
 // outgoing RPCs.
 // TODO(hpucha): Enhance to add versioning, scrub Approximation content for privacy.
 func Match(ctx *context.T, p security.BlessingPattern, hint ApproximationType, visitedGroups map[string]struct{}, blessings map[string]struct{}) (map[string]struct{}, []Approximation) {
 	if visitedGroups == nil {
 		visitedGroups = make(map[string]struct{})
 	}

 	g := &grpClient{
 		hint:       hint,
 		visited:    visitedGroups,
 		rpcHandler: groupClientRPCImpl{},
 	}
 	return g.match(ctx, p, blessings), g.apprxs
 }

 type grpClient struct {
 	hint       ApproximationType
 	version    string
 	visited    map[string]struct{}
 	apprxs     []Approximation
 	rpcHandler groupClientRPC
 }

 func (g *grpClient) match(ctx *context.T, p security.BlessingPattern, blessings map[string]struct{}) map[string]struct{} {
 	if len(p) == 0 {
 		return nil
 	}

 	// Note: The correct answer here is that the returned set must
 	// consist of exactMatch and every proper suffix of the
 	// blessing string. Since we do not allow any components after
 	// security.AllPrincipals, returning exactMatch is sufficient.
 	if p == security.AllPrincipals {
 		return exactMatch
 	}

 	patTokens, err := splitPattern(p)
 	if err != nil {
 		// Approximate the result.
 		errTmp := verror.New(verror.ErrBadArg, ctx, "malformed pattern", p)
 		g.apprxs = append(g.apprxs, Approximation{Reason: string(verror.ErrorID(errTmp)), Details: errTmp.Error()})
 		return approxRemainder(g.hint, blessings)
 	}

 	glob := true
 	if patTokens[len(patTokens)-1] == string(security.NoExtension) {
 		glob = false
 		patTokens = patTokens[:len(patTokens)-1]
 	}

 	remainder := make(map[string]struct{})
 	for b := range blessings {
 		rem := g.matchedByBlessing(ctx, patTokens, b)

 		if glob {
 			remainder = union(remainder, rem)
 			continue
 		}

 		for s := range rem {
 			if s == "" {
 				remainder = union(remainder, exactMatch)
 				break
 			}
 		}
 	}
 	return remainder
 }

 func (g *grpClient) matchedByBlessing(ctx *context.T, patTokens []string, b string) map[string]struct{} {
 	remainder := convertToSet(b)

 	for _, patTok := range patTokens {

 		removeEmptyStrings(remainder)
 		if len(remainder) == 0 {
 			return nil
 		}

 		if group := groupName(patTok); group != "" {
 			remainder = g.remainder(ctx, group, remainder)
 			continue
 		}

 		// Pattern token is not a group reference.
 		newRemainder := make(map[string]struct{})
 		for b := range remainder {
 			btok, suffix := leftMostToken(b)
 			if patTok == btok {
 				newRemainder[suffix] = struct{}{}
 			}
 		}
 		remainder = newRemainder
 	}

 	return remainder
 }

 func (g *grpClient) remainder(ctx *context.T, groupName string, blessingChunks map[string]struct{}) map[string]struct{} {
 	var err error
 	var apprxs []Approximation
 	var remainder map[string]struct{}

 	if _, ok := g.visited[groupName]; ok {
 		err = verror.New(ErrCycleFound, ctx, groupName, g.visited)
 	} else {
 		visited := copyMap(g.visited)
 		visited[groupName] = struct{}{}
 		remainder, apprxs, _, err = g.rpcHandler.relate(ctx, groupName, blessingChunks, g.hint, g.version, visited)
 	}

 	g.apprxs = append(g.apprxs, apprxs...)
 	if err != nil {
 		// For any error, suitably approximate the result.
 		g.apprxs = append(g.apprxs, Approximation{Reason: string(verror.ErrorID(err)), Details: err.Error()})
 		return approxRemainder(g.hint, blessingChunks)
 	}

 	return remainder
 }

 ///////////////////////////////
 // Helper functions

 // splitPattern splits a pattern into valid tokens separated by ":"
 // (security.ChainSeparator). If any token in a pattern is invalid, it returns
 // an error.
 //
 // A group token (<grp:[grpname]>) is treated as indivisible. A pattern token
 // is valid if it is a valid blessing extension or a single valid group token.
 // A token that concatenates two group tokens, or a group token concatenated
 // with a valid blessing extension, is invalid.
 //
 // TODO(hpucha): Is there a better way to do this split using regex
 // matching?
 func splitPattern(p security.BlessingPattern) ([]string, error) {
 	// Check that the blessing pattern is valid without the
 	// presence of group tokens (see v23/security/pattern.go).
 	if pTmp := security.BlessingPattern(grpRegexp.ReplaceAllLiteralString(string(p), "X")); !pTmp.IsValid() {
 		return nil, errors.New("invalid pattern: non-group tokens are invalid")
 	}

 	pStr := string(p)
 	var patTokens []string

 	for pStr != "" {
 		tokens := strings.SplitN(pStr, security.ChainSeparator, 2)

 		if !strings.Contains(tokens[0], grpStartToken) {
 			// Token is a blessing extension.
 			patTokens = append(patTokens, tokens[0])
 			if len(tokens) != 2 {
 				break
 			}
 			pStr = tokens[1]
 			continue
 		}

 		// Check for a valid group token.
 		if !strings.HasPrefix(tokens[0], grpStartToken) {
 			// Invalid group token. <grp: is not at the beginning of a token.
 			return nil, errors.New("invalid pattern: group token has a prefix")
 		}

 		endpos := strings.Index(pStr, GroupEnd)

 		if endpos < 0 {
 			// Invalid group token. Matching ">" not found.
 			return nil, errors.New("invalid pattern: group end delimiter not found")
 		}

 		if endpos < len(pStr)-1 && pStr[endpos+1] != security.ChainSeparator[0] {
 			// The pattern must either end here, or be followed by a /.
 			return nil, errors.New("invalid pattern: group token has a suffix")
 		}

 		grpName := pStr[len(GroupStart):endpos]
 		if grpName == "" {
 			return nil, errors.New("invalid pattern: group token is empty")
 		}
 		patTokens = append(patTokens, pStr[0:endpos+1])

 		// Skip the / and check if any string is remaining.
 		if endpos+2 >= len(pStr) {
 			return patTokens, nil
 		}

 		pStr = pStr[endpos+2:]
 	}
 	return patTokens, nil
 }

 // groupName extracts the group name from a pattern token.
 func groupName(pattok string) string {
 	if strings.HasPrefix(pattok, GroupStart) && strings.HasSuffix(pattok, GroupEnd) {
 		return pattok[len(GroupStart) : len(pattok)-len(GroupEnd)]
 	}
 	return ""
 }

 // leftMostToken returns the left most token and the remaining suffix
 // of a blessing name.
 func leftMostToken(b string) (string, string) {
 	tokens := strings.SplitN(b, security.ChainSeparator, 2)
 	suffix := ""
 	if len(tokens) == 2 {
 		suffix = tokens[1]
 	}
 	return tokens[0], suffix
 }

 // removeEmptyStrings removes any empty blessing chunks from the
 // remainder set.
 func removeEmptyStrings(remainder map[string]struct{}) {
 	for b := range remainder {
 		if b == "" {
 			delete(remainder, b)
 		}
 	}
 }

 func copyMap(in map[string]struct{}) map[string]struct{} {
 	out := make(map[string]struct{}, len(in))
 	for k := range in {
 		out[k] = struct{}{}
 	}
 	return out
 }

 func approxRemainder(hint ApproximationType, blessingChunks map[string]struct{}) map[string]struct{} {
 	if hint == ApproximationTypeUnder {
 		return nil
 	}

 	remainder := make(map[string]struct{})
 	for bc := range blessingChunks {
 		properSuffixes(remainder, bc)
 	}
 	return remainder
 }

 func properSuffixes(suffixes map[string]struct{}, bc string) {
 	parts := strings.SplitN(bc, security.ChainSeparator, 2)
 	for len(parts) == 2 {
 		suffixes[parts[1]] = struct{}{}
 		parts = strings.SplitN(parts[1], security.ChainSeparator, 2)
 	}
 	suffixes[""] = struct{}{}
 }

 // union merges set s2 into s1 and returns s1.
 func union(s1, s2 map[string]struct{}) map[string]struct{} {
 	for k := range s2 {
 		s1[k] = struct{}{}
 	}
 	return s1
 }

 // groupClientRPC is the interface for the group client making the Relate RPC.
 //
 // Used for faking RPC handling in tests.
 // TODO(hpucha/ashankar): Investigate if injecting a mock rpc.Client for tests is possible.
 type groupClientRPC interface {
 	relate(ctx *context.T, groupName string, blessingChunks map[string]struct{}, hint ApproximationType, version string, vGrps map[string]struct{}) (map[string]struct{}, []Approximation, string, error)
 }

 type groupClientRPCImpl struct{}

 func (g groupClientRPCImpl) relate(ctx *context.T, groupName string, blessingChunks map[string]struct{}, hint ApproximationType, version string, vGrps map[string]struct{}) (map[string]struct{}, []Approximation, string, error) {
 	client := GroupClient(groupName)
 	return client.Relate(ctx, blessingChunks, hint, version, vGrps)
 }
	// Copyright 2015 The Vanadium Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style
	// license that can be found in the LICENSE file.

	// This is WIP to implement and test algorithms that match blessings
	// against blessing patterns that involve groups. We expect to
	// eventually migrate some of this code to v23/security/pattern.go.

	package groups

	import (
	"errors"
	"regexp"
	"strings"

	"v.io/v23/context"
	"v.io/v23/security"
	"v.io/v23/verror"
	)

	const (
	GroupStart = "<grp:" // GroupStart indicates the start of a group name in a blessing pattern.
	GroupEnd = ">" // GroupEnd indicates the end of a group name in a blessing pattern.
	)

	var (
	exactMatch = convertToSet("")
	grpRegexp = regexp.MustCompile(GroupStart + "[^" + GroupEnd + "]*" + GroupEnd)
	grpStartToken = strings.TrimSuffix(GroupStart, security.ChainSeparator)
	)

	// Match matches blessing names against a pattern. It returns an empty array if
	// the presented blessing names do not match the pattern, or a set of suffixes
	// when the pattern is a prefix of the blessing names. Match approximates the
	// result if any errors are encountered during the matching process.
	//
	// Match assumes presented blessing names are valid. ctx is used to make any
	// outgoing RPCs.
	// TODO(hpucha): Enhance to add versioning, scrub Approximation content for privacy.
	func Match(ctx *context.T, p security.BlessingPattern, hint ApproximationType, visitedGroups map[string]struct{}, blessings map[string]struct{}) (map[string]struct{}, []Approximation) {
	if visitedGroups == nil {
	visitedGroups = make(map[string]struct{})
	}

	g := &grpClient{
	hint: hint,
	visited: visitedGroups,
	rpcHandler: groupClientRPCImpl{},
	}
	return g.match(ctx, p, blessings), g.apprxs
	}

	type grpClient struct {
	hint ApproximationType
	version string
	visited map[string]struct{}
	apprxs []Approximation
	rpcHandler groupClientRPC
	}

	func (g grpClient) match(ctx context.T, p security.BlessingPattern, blessings map[string]struct{}) map[string]struct{} {
	if len(p) == 0 {
	return nil
	}

	// Note: The correct answer here is that the returned set must
	// consist of exactMatch and every proper suffix of the
	// blessing string. Since we do not allow any components after
	// security.AllPrincipals, returning exactMatch is sufficient.
	if p == security.AllPrincipals {
	return exactMatch
	}

	patTokens, err := splitPattern(p)
	if err != nil {
	// Approximate the result.
	errTmp := verror.New(verror.ErrBadArg, ctx, "malformed pattern", p)
	g.apprxs = append(g.apprxs, Approximation{Reason: string(verror.ErrorID(errTmp)), Details: errTmp.Error()})
	return approxRemainder(g.hint, blessings)
	}

	glob := true
	if patTokens[len(patTokens)-1] == string(security.NoExtension) {
	glob = false
	patTokens = patTokens[:len(patTokens)-1]
	}

	remainder := make(map[string]struct{})
	for b := range blessings {
	rem := g.matchedByBlessing(ctx, patTokens, b)

	if glob {
	remainder = union(remainder, rem)
	continue
	}

	for s := range rem {
	if s == "" {
	remainder = union(remainder, exactMatch)
	break
	}
	}
	}
	return remainder
	}

	func (g grpClient) matchedByBlessing(ctx context.T, patTokens []string, b string) map[string]struct{} {
	remainder := convertToSet(b)

	for _, patTok := range patTokens {

	removeEmptyStrings(remainder)
	if len(remainder) == 0 {
	return nil
	}

	if group := groupName(patTok); group != "" {
	remainder = g.remainder(ctx, group, remainder)
	continue
	}

	// Pattern token is not a group reference.
	newRemainder := make(map[string]struct{})
	for b := range remainder {
	btok, suffix := leftMostToken(b)
	if patTok == btok {
	newRemainder[suffix] = struct{}{}
	}
	}
	remainder = newRemainder
	}

	return remainder
	}

	func (g grpClient) remainder(ctx context.T, groupName string, blessingChunks map[string]struct{}) map[string]struct{} {
	var err error
	var apprxs []Approximation
	var remainder map[string]struct{}

	if _, ok := g.visited[groupName]; ok {
	err = verror.New(ErrCycleFound, ctx, groupName, g.visited)
	} else {
	visited := copyMap(g.visited)
	visited[groupName] = struct{}{}
	remainder, apprxs, _, err = g.rpcHandler.relate(ctx, groupName, blessingChunks, g.hint, g.version, visited)
	}

	g.apprxs = append(g.apprxs, apprxs...)
	if err != nil {
	// For any error, suitably approximate the result.
	g.apprxs = append(g.apprxs, Approximation{Reason: string(verror.ErrorID(err)), Details: err.Error()})
	return approxRemainder(g.hint, blessingChunks)
	}

	return remainder
	}

	///////////////////////////////
	// Helper functions

	// splitPattern splits a pattern into valid tokens separated by ":"
	// (security.ChainSeparator). If any token in a pattern is invalid, it returns
	// an error.
	//
	// A group token (<grp:[grpname]>) is treated as indivisible. A pattern token
	// is valid if it is a valid blessing extension or a single valid group token.
	// A token that concatenates two group tokens, or a group token concatenated
	// with a valid blessing extension, is invalid.
	//
	// TODO(hpucha): Is there a better way to do this split using regex
	// matching?
	func splitPattern(p security.BlessingPattern) ([]string, error) {
	// Check that the blessing pattern is valid without the
	// presence of group tokens (see v23/security/pattern.go).
	if pTmp := security.BlessingPattern(grpRegexp.ReplaceAllLiteralString(string(p), "X")); !pTmp.IsValid() {
	return nil, errors.New("invalid pattern: non-group tokens are invalid")
	}

	pStr := string(p)
	var patTokens []string

	for pStr != "" {
	tokens := strings.SplitN(pStr, security.ChainSeparator, 2)

	if !strings.Contains(tokens[0], grpStartToken) {
	// Token is a blessing extension.
	patTokens = append(patTokens, tokens[0])
	if len(tokens) != 2 {
	break
	}
	pStr = tokens[1]
	continue
	}

	// Check for a valid group token.
	if !strings.HasPrefix(tokens[0], grpStartToken) {
	// Invalid group token. <grp: is not at the beginning of a token.
	return nil, errors.New("invalid pattern: group token has a prefix")
	}

	endpos := strings.Index(pStr, GroupEnd)

	if endpos < 0 {
	// Invalid group token. Matching ">" not found.
	return nil, errors.New("invalid pattern: group end delimiter not found")
	}

	if endpos < len(pStr)-1 && pStr[endpos+1] != security.ChainSeparator[0] {
	// The pattern must either end here, or be followed by a /.
	return nil, errors.New("invalid pattern: group token has a suffix")
	}

	grpName := pStr[len(GroupStart):endpos]
	if grpName == "" {
	return nil, errors.New("invalid pattern: group token is empty")
	}
	patTokens = append(patTokens, pStr[0:endpos+1])

	// Skip the / and check if any string is remaining.
	if endpos+2 >= len(pStr) {
	return patTokens, nil
	}

	pStr = pStr[endpos+2:]
	}
	return patTokens, nil
	}

	// groupName extracts the group name from a pattern token.
	func groupName(pattok string) string {
	if strings.HasPrefix(pattok, GroupStart) && strings.HasSuffix(pattok, GroupEnd) {
	return pattok[len(GroupStart) : len(pattok)-len(GroupEnd)]
	}
	return ""
	}

	// leftMostToken returns the left most token and the remaining suffix
	// of a blessing name.
	func leftMostToken(b string) (string, string) {
	tokens := strings.SplitN(b, security.ChainSeparator, 2)
	suffix := ""
	if len(tokens) == 2 {
	suffix = tokens[1]
	}
	return tokens[0], suffix
	}

	// removeEmptyStrings removes any empty blessing chunks from the
	// remainder set.
	func removeEmptyStrings(remainder map[string]struct{}) {
	for b := range remainder {
	if b == "" {
	delete(remainder, b)
	}
	}
	}

	func copyMap(in map[string]struct{}) map[string]struct{} {
	out := make(map[string]struct{}, len(in))
	for k := range in {
	out[k] = struct{}{}
	}
	return out
	}

	func approxRemainder(hint ApproximationType, blessingChunks map[string]struct{}) map[string]struct{} {
	if hint == ApproximationTypeUnder {
	return nil
	}

	remainder := make(map[string]struct{})
	for bc := range blessingChunks {
	properSuffixes(remainder, bc)
	}
	return remainder
	}

	func properSuffixes(suffixes map[string]struct{}, bc string) {
	parts := strings.SplitN(bc, security.ChainSeparator, 2)
	for len(parts) == 2 {
	suffixes[parts[1]] = struct{}{}
	parts = strings.SplitN(parts[1], security.ChainSeparator, 2)
	}
	suffixes[""] = struct{}{}
	}

	// union merges set s2 into s1 and returns s1.
	func union(s1, s2 map[string]struct{}) map[string]struct{} {
	for k := range s2 {
	s1[k] = struct{}{}
	}
	return s1
	}

	// groupClientRPC is the interface for the group client making the Relate RPC.
	//
	// Used for faking RPC handling in tests.
	// TODO(hpucha/ashankar): Investigate if injecting a mock rpc.Client for tests is possible.
	type groupClientRPC interface {
	relate(ctx *context.T, groupName string, blessingChunks map[string]struct{}, hint ApproximationType, version string, vGrps map[string]struct{}) (map[string]struct{}, []Approximation, string, error)
	}

	type groupClientRPCImpl struct{}

	func (g groupClientRPCImpl) relate(ctx *context.T, groupName string, blessingChunks map[string]struct{}, hint ApproximationType, version string, vGrps map[string]struct{}) (map[string]struct{}, []Approximation, string, error) {
	client := GroupClient(groupName)
	return client.Relate(ctx, blessingChunks, hint, version, vGrps)
	}