cmd/bpa-operator/vendor/github.com/grpc-ecosystem/grpc-gateway/runtime/pattern.go

   1 package runtime
   2
   3 import (
   4         "errors"
   5         "fmt"
   6         "strings"
   7
   8         "github.com/grpc-ecosystem/grpc-gateway/utilities"
   9         "google.golang.org/grpc/grpclog"
  10 )
  11
  12 var (
  13         // ErrNotMatch indicates that the given HTTP request path does not match to the pattern.
  14         ErrNotMatch = errors.New("not match to the path pattern")
  15         // ErrInvalidPattern indicates that the given definition of Pattern is not valid.
  16         ErrInvalidPattern = errors.New("invalid pattern")
  17 )
  18
  19 type op struct {
  20         code    utilities.OpCode
  21         operand int
  22 }
  23
  24 // Pattern is a template pattern of http request paths defined in github.com/googleapis/googleapis/google/api/http.proto.
  25 type Pattern struct {
  26         // ops is a list of operations
  27         ops []op
  28         // pool is a constant pool indexed by the operands or vars.
  29         pool []string
  30         // vars is a list of variables names to be bound by this pattern
  31         vars []string
  32         // stacksize is the max depth of the stack
  33         stacksize int
  34         // tailLen is the length of the fixed-size segments after a deep wildcard
  35         tailLen int
  36         // verb is the VERB part of the path pattern. It is empty if the pattern does not have VERB part.
  37         verb string
  38 }
  39
  40 // NewPattern returns a new Pattern from the given definition values.
  41 // "ops" is a sequence of op codes. "pool" is a constant pool.
  42 // "verb" is the verb part of the pattern. It is empty if the pattern does not have the part.
  43 // "version" must be 1 for now.
  44 // It returns an error if the given definition is invalid.
  45 func NewPattern(version int, ops []int, pool []string, verb string) (Pattern, error) {
  46         if version != 1 {
  47                 grpclog.Infof("unsupported version: %d", version)
  48                 return Pattern{}, ErrInvalidPattern
  49         }
  50
  51         l := len(ops)
  52         if l%2 != 0 {
  53                 grpclog.Infof("odd number of ops codes: %d", l)
  54                 return Pattern{}, ErrInvalidPattern
  55         }
  56
  57         var (
  58                 typedOps        []op
  59                 stack, maxstack int
  60                 tailLen         int
  61                 pushMSeen       bool
  62                 vars            []string
  63         )
  64         for i := 0; i < l; i += 2 {
  65                 op := op{code: utilities.OpCode(ops[i]), operand: ops[i+1]}
  66                 switch op.code {
  67                 case utilities.OpNop:
  68                         continue
  69                 case utilities.OpPush:
  70                         if pushMSeen {
  71                                 tailLen++
  72                         }
  73                         stack++
  74                 case utilities.OpPushM:
  75                         if pushMSeen {
  76                                 grpclog.Infof("pushM appears twice")
  77                                 return Pattern{}, ErrInvalidPattern
  78                         }
  79                         pushMSeen = true
  80                         stack++
  81                 case utilities.OpLitPush:
  82                         if op.operand < 0 || len(pool) <= op.operand {
  83                                 grpclog.Infof("negative literal index: %d", op.operand)
  84                                 return Pattern{}, ErrInvalidPattern
  85                         }
  86                         if pushMSeen {
  87                                 tailLen++
  88                         }
  89                         stack++
  90                 case utilities.OpConcatN:
  91                         if op.operand <= 0 {
  92                                 grpclog.Infof("negative concat size: %d", op.operand)
  93                                 return Pattern{}, ErrInvalidPattern
  94                         }
  95                         stack -= op.operand
  96                         if stack < 0 {
  97                                 grpclog.Print("stack underflow")
  98                                 return Pattern{}, ErrInvalidPattern
  99                         }
 100                         stack++
 101                 case utilities.OpCapture:
 102                         if op.operand < 0 || len(pool) <= op.operand {
 103                                 grpclog.Infof("variable name index out of bound: %d", op.operand)
 104                                 return Pattern{}, ErrInvalidPattern
 105                         }
 106                         v := pool[op.operand]
 107                         op.operand = len(vars)
 108                         vars = append(vars, v)
 109                         stack--
 110                         if stack < 0 {
 111                                 grpclog.Infof("stack underflow")
 112                                 return Pattern{}, ErrInvalidPattern
 113                         }
 114                 default:
 115                         grpclog.Infof("invalid opcode: %d", op.code)
 116                         return Pattern{}, ErrInvalidPattern
 117                 }
 118
 119                 if maxstack < stack {
 120                         maxstack = stack
 121                 }
 122                 typedOps = append(typedOps, op)
 123         }
 124         return Pattern{
 125                 ops:       typedOps,
 126                 pool:      pool,
 127                 vars:      vars,
 128                 stacksize: maxstack,
 129                 tailLen:   tailLen,
 130                 verb:      verb,
 131         }, nil
 132 }
 133
 134 // MustPattern is a helper function which makes it easier to call NewPattern in variable initialization.
 135 func MustPattern(p Pattern, err error) Pattern {
 136         if err != nil {
 137                 grpclog.Fatalf("Pattern initialization failed: %v", err)
 138         }
 139         return p
 140 }
 141
 142 // Match examines components if it matches to the Pattern.
 143 // If it matches, the function returns a mapping from field paths to their captured values.
 144 // If otherwise, the function returns an error.
 145 func (p Pattern) Match(components []string, verb string) (map[string]string, error) {
 146         if p.verb != verb {
 147                 return nil, ErrNotMatch
 148         }
 149
 150         var pos int
 151         stack := make([]string, 0, p.stacksize)
 152         captured := make([]string, len(p.vars))
 153         l := len(components)
 154         for _, op := range p.ops {
 155                 switch op.code {
 156                 case utilities.OpNop:
 157                         continue
 158                 case utilities.OpPush, utilities.OpLitPush:
 159                         if pos >= l {
 160                                 return nil, ErrNotMatch
 161                         }
 162                         c := components[pos]
 163                         if op.code == utilities.OpLitPush {
 164                                 if lit := p.pool[op.operand]; c != lit {
 165                                         return nil, ErrNotMatch
 166                                 }
 167                         }
 168                         stack = append(stack, c)
 169                         pos++
 170                 case utilities.OpPushM:
 171                         end := len(components)
 172                         if end < pos+p.tailLen {
 173                                 return nil, ErrNotMatch
 174                         }
 175                         end -= p.tailLen
 176                         stack = append(stack, strings.Join(components[pos:end], "/"))
 177                         pos = end
 178                 case utilities.OpConcatN:
 179                         n := op.operand
 180                         l := len(stack) - n
 181                         stack = append(stack[:l], strings.Join(stack[l:], "/"))
 182                 case utilities.OpCapture:
 183                         n := len(stack) - 1
 184                         captured[op.operand] = stack[n]
 185                         stack = stack[:n]
 186                 }
 187         }
 188         if pos < l {
 189                 return nil, ErrNotMatch
 190         }
 191         bindings := make(map[string]string)
 192         for i, val := range captured {
 193                 bindings[p.vars[i]] = val
 194         }
 195         return bindings, nil
 196 }
 197
 198 // Verb returns the verb part of the Pattern.
 199 func (p Pattern) Verb() string { return p.verb }
 200
 201 func (p Pattern) String() string {
 202         var stack []string
 203         for _, op := range p.ops {
 204                 switch op.code {
 205                 case utilities.OpNop:
 206                         continue
 207                 case utilities.OpPush:
 208                         stack = append(stack, "*")
 209                 case utilities.OpLitPush:
 210                         stack = append(stack, p.pool[op.operand])
 211                 case utilities.OpPushM:
 212                         stack = append(stack, "**")
 213                 case utilities.OpConcatN:
 214                         n := op.operand
 215                         l := len(stack) - n
 216                         stack = append(stack[:l], strings.Join(stack[l:], "/"))
 217                 case utilities.OpCapture:
 218                         n := len(stack) - 1
 219                         stack[n] = fmt.Sprintf("{%s=%s}", p.vars[op.operand], stack[n])
 220                 }
 221         }
 222         segs := strings.Join(stack, "/")
 223         if p.verb != "" {
 224                 return fmt.Sprintf("/%s:%s", segs, p.verb)
 225         }
 226         return "/" + segs
 227 }