pattern.go

Documentation: github.com/grpc-ecosystem/grpc-gateway/v2/runtime

     1  package runtime
     2  
     3  import (
     4  	"errors"
     5  	"fmt"
     6  	"strconv"
     7  	"strings"
     8  
     9  	"github.com/grpc-ecosystem/grpc-gateway/v2/utilities"
    10  	"google.golang.org/grpc/grpclog"
    11  )
    12  
    13  var (
    14  	// ErrNotMatch indicates that the given HTTP request path does not match to the pattern.
    15  	ErrNotMatch = errors.New("not match to the path pattern")
    16  	// ErrInvalidPattern indicates that the given definition of Pattern is not valid.
    17  	ErrInvalidPattern = errors.New("invalid pattern")
    18  )
    19  
    20  type MalformedSequenceError string
    21  
    22  func (e MalformedSequenceError) Error() string {
    23  	return "malformed path escape " + strconv.Quote(string(e))
    24  }
    25  
    26  type op struct {
    27  	code    utilities.OpCode
    28  	operand int
    29  }
    30  
    31  // Pattern is a template pattern of http request paths defined in
    32  // https://github.com/googleapis/googleapis/blob/master/google/api/http.proto
    33  type Pattern struct {
    34  	// ops is a list of operations
    35  	ops []op
    36  	// pool is a constant pool indexed by the operands or vars.
    37  	pool []string
    38  	// vars is a list of variables names to be bound by this pattern
    39  	vars []string
    40  	// stacksize is the max depth of the stack
    41  	stacksize int
    42  	// tailLen is the length of the fixed-size segments after a deep wildcard
    43  	tailLen int
    44  	// verb is the VERB part of the path pattern. It is empty if the pattern does not have VERB part.
    45  	verb string
    46  }
    47  
    48  // NewPattern returns a new Pattern from the given definition values.
    49  // "ops" is a sequence of op codes. "pool" is a constant pool.
    50  // "verb" is the verb part of the pattern. It is empty if the pattern does not have the part.
    51  // "version" must be 1 for now.
    52  // It returns an error if the given definition is invalid.
    53  func NewPattern(version int, ops []int, pool []string, verb string) (Pattern, error) {
    54  	if version != 1 {
    55  		grpclog.Infof("unsupported version: %d", version)
    56  		return Pattern{}, ErrInvalidPattern
    57  	}
    58  
    59  	l := len(ops)
    60  	if l%2 != 0 {
    61  		grpclog.Infof("odd number of ops codes: %d", l)
    62  		return Pattern{}, ErrInvalidPattern
    63  	}
    64  
    65  	var (
    66  		typedOps        []op
    67  		stack, maxstack int
    68  		tailLen         int
    69  		pushMSeen       bool
    70  		vars            []string
    71  	)
    72  	for i := 0; i < l; i += 2 {
    73  		op := op{code: utilities.OpCode(ops[i]), operand: ops[i+1]}
    74  		switch op.code {
    75  		case utilities.OpNop:
    76  			continue
    77  		case utilities.OpPush:
    78  			if pushMSeen {
    79  				tailLen++
    80  			}
    81  			stack++
    82  		case utilities.OpPushM:
    83  			if pushMSeen {
    84  				grpclog.Infof("pushM appears twice")
    85  				return Pattern{}, ErrInvalidPattern
    86  			}
    87  			pushMSeen = true
    88  			stack++
    89  		case utilities.OpLitPush:
    90  			if op.operand < 0 || len(pool) <= op.operand {
    91  				grpclog.Infof("negative literal index: %d", op.operand)
    92  				return Pattern{}, ErrInvalidPattern
    93  			}
    94  			if pushMSeen {
    95  				tailLen++
    96  			}
    97  			stack++
    98  		case utilities.OpConcatN:
    99  			if op.operand <= 0 {
   100  				grpclog.Infof("negative concat size: %d", op.operand)
   101  				return Pattern{}, ErrInvalidPattern
   102  			}
   103  			stack -= op.operand
   104  			if stack < 0 {
   105  				grpclog.Info("stack underflow")
   106  				return Pattern{}, ErrInvalidPattern
   107  			}
   108  			stack++
   109  		case utilities.OpCapture:
   110  			if op.operand < 0 || len(pool) <= op.operand {
   111  				grpclog.Infof("variable name index out of bound: %d", op.operand)
   112  				return Pattern{}, ErrInvalidPattern
   113  			}
   114  			v := pool[op.operand]
   115  			op.operand = len(vars)
   116  			vars = append(vars, v)
   117  			stack--
   118  			if stack < 0 {
   119  				grpclog.Infof("stack underflow")
   120  				return Pattern{}, ErrInvalidPattern
   121  			}
   122  		default:
   123  			grpclog.Infof("invalid opcode: %d", op.code)
   124  			return Pattern{}, ErrInvalidPattern
   125  		}
   126  
   127  		if maxstack < stack {
   128  			maxstack = stack
   129  		}
   130  		typedOps = append(typedOps, op)
   131  	}
   132  	return Pattern{
   133  		ops:       typedOps,
   134  		pool:      pool,
   135  		vars:      vars,
   136  		stacksize: maxstack,
   137  		tailLen:   tailLen,
   138  		verb:      verb,
   139  	}, nil
   140  }
   141  
   142  // MustPattern is a helper function which makes it easier to call NewPattern in variable initialization.
   143  func MustPattern(p Pattern, err error) Pattern {
   144  	if err != nil {
   145  		grpclog.Fatalf("Pattern initialization failed: %v", err)
   146  	}
   147  	return p
   148  }
   149  
   150  // MatchAndEscape examines components to determine if they match to a Pattern.
   151  // MatchAndEscape will return an error if no Patterns matched or if a pattern
   152  // matched but contained malformed escape sequences. If successful, the function
   153  // returns a mapping from field paths to their captured values.
   154  func (p Pattern) MatchAndEscape(components []string, verb string, unescapingMode UnescapingMode) (map[string]string, error) {
   155  	if p.verb != verb {
   156  		if p.verb != "" {
   157  			return nil, ErrNotMatch
   158  		}
   159  		if len(components) == 0 {
   160  			components = []string{":" + verb}
   161  		} else {
   162  			components = append([]string{}, components...)
   163  			components[len(components)-1] += ":" + verb
   164  		}
   165  	}
   166  
   167  	var pos int
   168  	stack := make([]string, 0, p.stacksize)
   169  	captured := make([]string, len(p.vars))
   170  	l := len(components)
   171  	for _, op := range p.ops {
   172  		var err error
   173  
   174  		switch op.code {
   175  		case utilities.OpNop:
   176  			continue
   177  		case utilities.OpPush, utilities.OpLitPush:
   178  			if pos >= l {
   179  				return nil, ErrNotMatch
   180  			}
   181  			c := components[pos]
   182  			if op.code == utilities.OpLitPush {
   183  				if lit := p.pool[op.operand]; c != lit {
   184  					return nil, ErrNotMatch
   185  				}
   186  			} else if op.code == utilities.OpPush {
   187  				if c, err = unescape(c, unescapingMode, false); err != nil {
   188  					return nil, err
   189  				}
   190  			}
   191  			stack = append(stack, c)
   192  			pos++
   193  		case utilities.OpPushM:
   194  			end := len(components)
   195  			if end < pos+p.tailLen {
   196  				return nil, ErrNotMatch
   197  			}
   198  			end -= p.tailLen
   199  			c := strings.Join(components[pos:end], "/")
   200  			if c, err = unescape(c, unescapingMode, true); err != nil {
   201  				return nil, err
   202  			}
   203  			stack = append(stack, c)
   204  			pos = end
   205  		case utilities.OpConcatN:
   206  			n := op.operand
   207  			l := len(stack) - n
   208  			stack = append(stack[:l], strings.Join(stack[l:], "/"))
   209  		case utilities.OpCapture:
   210  			n := len(stack) - 1
   211  			captured[op.operand] = stack[n]
   212  			stack = stack[:n]
   213  		}
   214  	}
   215  	if pos < l {
   216  		return nil, ErrNotMatch
   217  	}
   218  	bindings := make(map[string]string)
   219  	for i, val := range captured {
   220  		bindings[p.vars[i]] = val
   221  	}
   222  	return bindings, nil
   223  }
   224  
   225  // MatchAndEscape examines components to determine if they match to a Pattern.
   226  // It will never perform per-component unescaping (see: UnescapingModeLegacy).
   227  // MatchAndEscape will return an error if no Patterns matched. If successful,
   228  // the function returns a mapping from field paths to their captured values.
   229  //
   230  // Deprecated: Use MatchAndEscape.
   231  func (p Pattern) Match(components []string, verb string) (map[string]string, error) {
   232  	return p.MatchAndEscape(components, verb, UnescapingModeDefault)
   233  }
   234  
   235  // Verb returns the verb part of the Pattern.
   236  func (p Pattern) Verb() string { return p.verb }
   237  
   238  func (p Pattern) String() string {
   239  	var stack []string
   240  	for _, op := range p.ops {
   241  		switch op.code {
   242  		case utilities.OpNop:
   243  			continue
   244  		case utilities.OpPush:
   245  			stack = append(stack, "*")
   246  		case utilities.OpLitPush:
   247  			stack = append(stack, p.pool[op.operand])
   248  		case utilities.OpPushM:
   249  			stack = append(stack, "**")
   250  		case utilities.OpConcatN:
   251  			n := op.operand
   252  			l := len(stack) - n
   253  			stack = append(stack[:l], strings.Join(stack[l:], "/"))
   254  		case utilities.OpCapture:
   255  			n := len(stack) - 1
   256  			stack[n] = fmt.Sprintf("{%s=%s}", p.vars[op.operand], stack[n])
   257  		}
   258  	}
   259  	segs := strings.Join(stack, "/")
   260  	if p.verb != "" {
   261  		return fmt.Sprintf("/%s:%s", segs, p.verb)
   262  	}
   263  	return "/" + segs
   264  }
   265  
   266  /*
   267   * The following code is adopted and modified from Go's standard library
   268   * and carries the attached license.
   269   *
   270   *     Copyright 2009 The Go Authors. All rights reserved.
   271   *     Use of this source code is governed by a BSD-style
   272   *     license that can be found in the LICENSE file.
   273   */
   274  
   275  // ishex returns whether or not the given byte is a valid hex character
   276  func ishex(c byte) bool {
   277  	switch {
   278  	case '0' <= c && c <= '9':
   279  		return true
   280  	case 'a' <= c && c <= 'f':
   281  		return true
   282  	case 'A' <= c && c <= 'F':
   283  		return true
   284  	}
   285  	return false
   286  }
   287  
   288  func isRFC6570Reserved(c byte) bool {
   289  	switch c {
   290  	case '!', '#', '$', '&', '\'', '(', ')', '*',
   291  		'+', ',', '/', ':', ';', '=', '?', '@', '[', ']':
   292  		return true
   293  	default:
   294  		return false
   295  	}
   296  }
   297  
   298  // unhex converts a hex point to the bit representation
   299  func unhex(c byte) byte {
   300  	switch {
   301  	case '0' <= c && c <= '9':
   302  		return c - '0'
   303  	case 'a' <= c && c <= 'f':
   304  		return c - 'a' + 10
   305  	case 'A' <= c && c <= 'F':
   306  		return c - 'A' + 10
   307  	}
   308  	return 0
   309  }
   310  
   311  // shouldUnescapeWithMode returns true if the character is escapable with the
   312  // given mode
   313  func shouldUnescapeWithMode(c byte, mode UnescapingMode) bool {
   314  	switch mode {
   315  	case UnescapingModeAllExceptReserved:
   316  		if isRFC6570Reserved(c) {
   317  			return false
   318  		}
   319  	case UnescapingModeAllExceptSlash:
   320  		if c == '/' {
   321  			return false
   322  		}
   323  	case UnescapingModeAllCharacters:
   324  		return true
   325  	}
   326  	return true
   327  }
   328  
   329  // unescape unescapes a path string using the provided mode
   330  func unescape(s string, mode UnescapingMode, multisegment bool) (string, error) {
   331  	// TODO(v3): remove UnescapingModeLegacy
   332  	if mode == UnescapingModeLegacy {
   333  		return s, nil
   334  	}
   335  
   336  	if !multisegment {
   337  		mode = UnescapingModeAllCharacters
   338  	}
   339  
   340  	// Count %, check that they're well-formed.
   341  	n := 0
   342  	for i := 0; i < len(s); {
   343  		if s[i] == '%' {
   344  			n++
   345  			if i+2 >= len(s) || !ishex(s[i+1]) || !ishex(s[i+2]) {
   346  				s = s[i:]
   347  				if len(s) > 3 {
   348  					s = s[:3]
   349  				}
   350  
   351  				return "", MalformedSequenceError(s)
   352  			}
   353  			i += 3
   354  		} else {
   355  			i++
   356  		}
   357  	}
   358  
   359  	if n == 0 {
   360  		return s, nil
   361  	}
   362  
   363  	var t strings.Builder
   364  	t.Grow(len(s))
   365  	for i := 0; i < len(s); i++ {
   366  		switch s[i] {
   367  		case '%':
   368  			c := unhex(s[i+1])<<4 | unhex(s[i+2])
   369  			if shouldUnescapeWithMode(c, mode) {
   370  				t.WriteByte(c)
   371  				i += 2
   372  				continue
   373  			}
   374  			fallthrough
   375  		default:
   376  			t.WriteByte(s[i])
   377  		}
   378  	}
   379  
   380  	return t.String(), nil
   381  }
   382
View as plain text