blob: 09053695da7ebe4e462f646aacc017587305c87c [file] [log] [blame]
Matteo Scandoloa6a3aee2019-11-26 13:30:14 -07001package runtime
2
3import (
4 "errors"
5 "fmt"
6 "strings"
7
8 "github.com/grpc-ecosystem/grpc-gateway/utilities"
9 "google.golang.org/grpc/grpclog"
10)
11
12var (
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
19type 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.
25type 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 // assumeColonVerb indicates whether a path suffix after a final
39 // colon may only be interpreted as a verb.
40 assumeColonVerb bool
41}
42
43type patternOptions struct {
44 assumeColonVerb bool
45}
46
47// PatternOpt is an option for creating Patterns.
48type PatternOpt func(*patternOptions)
49
50// NewPattern returns a new Pattern from the given definition values.
51// "ops" is a sequence of op codes. "pool" is a constant pool.
52// "verb" is the verb part of the pattern. It is empty if the pattern does not have the part.
53// "version" must be 1 for now.
54// It returns an error if the given definition is invalid.
55func NewPattern(version int, ops []int, pool []string, verb string, opts ...PatternOpt) (Pattern, error) {
56 options := patternOptions{
57 assumeColonVerb: true,
58 }
59 for _, o := range opts {
60 o(&options)
61 }
62
63 if version != 1 {
64 grpclog.Infof("unsupported version: %d", version)
65 return Pattern{}, ErrInvalidPattern
66 }
67
68 l := len(ops)
69 if l%2 != 0 {
70 grpclog.Infof("odd number of ops codes: %d", l)
71 return Pattern{}, ErrInvalidPattern
72 }
73
74 var (
75 typedOps []op
76 stack, maxstack int
77 tailLen int
78 pushMSeen bool
79 vars []string
80 )
81 for i := 0; i < l; i += 2 {
82 op := op{code: utilities.OpCode(ops[i]), operand: ops[i+1]}
83 switch op.code {
84 case utilities.OpNop:
85 continue
86 case utilities.OpPush:
87 if pushMSeen {
88 tailLen++
89 }
90 stack++
91 case utilities.OpPushM:
92 if pushMSeen {
93 grpclog.Infof("pushM appears twice")
94 return Pattern{}, ErrInvalidPattern
95 }
96 pushMSeen = true
97 stack++
98 case utilities.OpLitPush:
99 if op.operand < 0 || len(pool) <= op.operand {
100 grpclog.Infof("negative literal index: %d", op.operand)
101 return Pattern{}, ErrInvalidPattern
102 }
103 if pushMSeen {
104 tailLen++
105 }
106 stack++
107 case utilities.OpConcatN:
108 if op.operand <= 0 {
109 grpclog.Infof("negative concat size: %d", op.operand)
110 return Pattern{}, ErrInvalidPattern
111 }
112 stack -= op.operand
113 if stack < 0 {
114 grpclog.Print("stack underflow")
115 return Pattern{}, ErrInvalidPattern
116 }
117 stack++
118 case utilities.OpCapture:
119 if op.operand < 0 || len(pool) <= op.operand {
120 grpclog.Infof("variable name index out of bound: %d", op.operand)
121 return Pattern{}, ErrInvalidPattern
122 }
123 v := pool[op.operand]
124 op.operand = len(vars)
125 vars = append(vars, v)
126 stack--
127 if stack < 0 {
128 grpclog.Infof("stack underflow")
129 return Pattern{}, ErrInvalidPattern
130 }
131 default:
132 grpclog.Infof("invalid opcode: %d", op.code)
133 return Pattern{}, ErrInvalidPattern
134 }
135
136 if maxstack < stack {
137 maxstack = stack
138 }
139 typedOps = append(typedOps, op)
140 }
141 return Pattern{
142 ops: typedOps,
143 pool: pool,
144 vars: vars,
145 stacksize: maxstack,
146 tailLen: tailLen,
147 verb: verb,
148 assumeColonVerb: options.assumeColonVerb,
149 }, nil
150}
151
152// MustPattern is a helper function which makes it easier to call NewPattern in variable initialization.
153func MustPattern(p Pattern, err error) Pattern {
154 if err != nil {
155 grpclog.Fatalf("Pattern initialization failed: %v", err)
156 }
157 return p
158}
159
160// Match examines components if it matches to the Pattern.
161// If it matches, the function returns a mapping from field paths to their captured values.
162// If otherwise, the function returns an error.
163func (p Pattern) Match(components []string, verb string) (map[string]string, error) {
164 if p.verb != verb {
165 if p.assumeColonVerb || p.verb != "" {
166 return nil, ErrNotMatch
167 }
168 if len(components) == 0 {
169 components = []string{":" + verb}
170 } else {
171 components = append([]string{}, components...)
172 components[len(components)-1] += ":" + verb
173 }
174 verb = ""
175 }
176
177 var pos int
178 stack := make([]string, 0, p.stacksize)
179 captured := make([]string, len(p.vars))
180 l := len(components)
181 for _, op := range p.ops {
182 switch op.code {
183 case utilities.OpNop:
184 continue
185 case utilities.OpPush, utilities.OpLitPush:
186 if pos >= l {
187 return nil, ErrNotMatch
188 }
189 c := components[pos]
190 if op.code == utilities.OpLitPush {
191 if lit := p.pool[op.operand]; c != lit {
192 return nil, ErrNotMatch
193 }
194 }
195 stack = append(stack, c)
196 pos++
197 case utilities.OpPushM:
198 end := len(components)
199 if end < pos+p.tailLen {
200 return nil, ErrNotMatch
201 }
202 end -= p.tailLen
203 stack = append(stack, strings.Join(components[pos:end], "/"))
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// Verb returns the verb part of the Pattern.
226func (p Pattern) Verb() string { return p.verb }
227
228func (p Pattern) String() string {
229 var stack []string
230 for _, op := range p.ops {
231 switch op.code {
232 case utilities.OpNop:
233 continue
234 case utilities.OpPush:
235 stack = append(stack, "*")
236 case utilities.OpLitPush:
237 stack = append(stack, p.pool[op.operand])
238 case utilities.OpPushM:
239 stack = append(stack, "**")
240 case utilities.OpConcatN:
241 n := op.operand
242 l := len(stack) - n
243 stack = append(stack[:l], strings.Join(stack[l:], "/"))
244 case utilities.OpCapture:
245 n := len(stack) - 1
246 stack[n] = fmt.Sprintf("{%s=%s}", p.vars[op.operand], stack[n])
247 }
248 }
249 segs := strings.Join(stack, "/")
250 if p.verb != "" {
251 return fmt.Sprintf("/%s:%s", segs, p.verb)
252 }
253 return "/" + segs
254}
255
256// AssumeColonVerbOpt indicates whether a path suffix after a final
257// colon may only be interpreted as a verb.
258func AssumeColonVerbOpt(val bool) PatternOpt {
259 return PatternOpt(func(o *patternOptions) {
260 o.assumeColonVerb = val
261 })
262}