podman

1
// Package denco provides fast URL router.
2
package denco
3

4
import (
5
	"fmt"
6
	"sort"
7
	"strings"
8
)
9

10
const (
11
	// ParamCharacter is a special character for path parameter.
12
	ParamCharacter = ':'
13

14
	// WildcardCharacter is a special character for wildcard path parameter.
15
	WildcardCharacter = '*'
16

17
	// TerminationCharacter is a special character for end of path.
18
	TerminationCharacter = '#'
19

20
	// SeparatorCharacter separates path segments.
21
	SeparatorCharacter = '/'
22

23
	// PathParamCharacter indicates a RESTCONF path param
24
	PathParamCharacter = '='
25

26
	// MaxSize is max size of records and internal slice.
27
	MaxSize = (1 << 22) - 1
28
)
29

30
// Router represents a URL router.
31
type Router struct {
32
	// SizeHint expects the maximum number of path parameters in records to Build.
33
	// SizeHint will be used to determine the capacity of the memory to allocate.
34
	// By default, SizeHint will be determined from given records to Build.
35
	SizeHint int
36

37
	static map[string]interface{}
38
	param  *doubleArray
39
}
40

41
// New returns a new Router.
42
func New() *Router {
43
	return &Router{
44
		SizeHint: -1,
45
		static:   make(map[string]interface{}),
46
		param:    newDoubleArray(),
47
	}
48
}
49

50
// Lookup returns data and path parameters that associated with path.
51
// params is a slice of the Param that arranged in the order in which parameters appeared.
52
// e.g. when built routing path is "/path/to/:id/:name" and given path is "/path/to/1/alice". params order is [{"id": "1"}, {"name": "alice"}], not [{"name": "alice"}, {"id": "1"}].
53
func (rt *Router) Lookup(path string) (data interface{}, params Params, found bool) {
54
	if data, found := rt.static[path]; found {
55
		return data, nil, true
56
	}
57
	if len(rt.param.node) == 1 {
58
		return nil, nil, false
59
	}
60
	nd, params, found := rt.param.lookup(path, make([]Param, 0, rt.SizeHint), 1)
61
	if !found {
62
		return nil, nil, false
63
	}
64
	for i := 0; i < len(params); i++ {
65
		params[i].Name = nd.paramNames[i]
66
	}
67
	return nd.data, params, true
68
}
69

70
// Build builds URL router from records.
71
func (rt *Router) Build(records []Record) error {
72
	statics, params := makeRecords(records)
73
	if len(params) > MaxSize {
74
		return fmt.Errorf("denco: too many records")
75
	}
76
	if rt.SizeHint < 0 {
77
		rt.SizeHint = 0
78
		for _, p := range params {
79
			size := 0
80
			for _, k := range p.Key {
81
				if k == ParamCharacter || k == WildcardCharacter {
82
					size++
83
				}
84
			}
85
			if size > rt.SizeHint {
86
				rt.SizeHint = size
87
			}
88
		}
89
	}
90
	for _, r := range statics {
91
		rt.static[r.Key] = r.Value
92
	}
93
	if err := rt.param.build(params, 1, 0, make(map[int]struct{})); err != nil {
94
		return err
95
	}
96
	return nil
97
}
98

99
// Param represents name and value of path parameter.
100
type Param struct {
101
	Name  string
102
	Value string
103
}
104

105
// Params represents the name and value of path parameters.
106
type Params []Param
107

108
// Get gets the first value associated with the given name.
109
// If there are no values associated with the key, Get returns "".
110
func (ps Params) Get(name string) string {
111
	for _, p := range ps {
112
		if p.Name == name {
113
			return p.Value
114
		}
115
	}
116
	return ""
117
}
118

119
type doubleArray struct {
120
	bc   []baseCheck
121
	node []*node
122
}
123

124
func newDoubleArray() *doubleArray {
125
	return &doubleArray{
126
		bc:   []baseCheck{0},
127
		node: []*node{nil}, // A start index is adjusting to 1 because 0 will be used as a mark of non-existent node.
128
	}
129
}
130

131
// baseCheck contains BASE, CHECK and Extra flags.
132
// From the top, 22bits of BASE, 2bits of Extra flags and 8bits of CHECK.
133
//
134
//  BASE (22bit) | Extra flags (2bit) | CHECK (8bit)
135
// |----------------------|--|--------|
136
// 32                    10  8         0
137
type baseCheck uint32
138

139
func (bc baseCheck) Base() int {
140
	return int(bc >> 10)
141
}
142

143
func (bc *baseCheck) SetBase(base int) {
144
	*bc |= baseCheck(base) << 10
145
}
146

147
func (bc baseCheck) Check() byte {
148
	return byte(bc)
149
}
150

151
func (bc *baseCheck) SetCheck(check byte) {
152
	*bc |= baseCheck(check)
153
}
154

155
func (bc baseCheck) IsEmpty() bool {
156
	return bc&0xfffffcff == 0
157
}
158

159
func (bc baseCheck) IsSingleParam() bool {
160
	return bc&paramTypeSingle == paramTypeSingle
161
}
162

163
func (bc baseCheck) IsWildcardParam() bool {
164
	return bc&paramTypeWildcard == paramTypeWildcard
165
}
166

167
func (bc baseCheck) IsAnyParam() bool {
168
	return bc&paramTypeAny != 0
169
}
170

171
func (bc *baseCheck) SetSingleParam() {
172
	*bc |= (1 << 8)
173
}
174

175
func (bc *baseCheck) SetWildcardParam() {
176
	*bc |= (1 << 9)
177
}
178

179
const (
180
	paramTypeSingle   = 0x0100
181
	paramTypeWildcard = 0x0200
182
	paramTypeAny      = 0x0300
183
)
184

185
func (da *doubleArray) lookup(path string, params []Param, idx int) (*node, []Param, bool) {
186
	indices := make([]uint64, 0, 1)
187
	for i := 0; i < len(path); i++ {
188
		if da.bc[idx].IsAnyParam() {
189
			indices = append(indices, (uint64(i)<<32)|(uint64(idx)&0xffffffff))
190
		}
191
		c := path[i]
192
		if idx = nextIndex(da.bc[idx].Base(), c); idx >= len(da.bc) || da.bc[idx].Check() != c {
193
			goto BACKTRACKING
194
		}
195
	}
196
	if next := nextIndex(da.bc[idx].Base(), TerminationCharacter); next < len(da.bc) && da.bc[next].Check() == TerminationCharacter {
197
		return da.node[da.bc[next].Base()], params, true
198
	}
199
BACKTRACKING:
200
	for j := len(indices) - 1; j >= 0; j-- {
201
		i, idx := int(indices[j]>>32), int(indices[j]&0xffffffff)
202
		if da.bc[idx].IsSingleParam() {
203
			idx := nextIndex(da.bc[idx].Base(), ParamCharacter)
204
			if idx >= len(da.bc) {
205
				break
206
			}
207
			next := NextSeparator(path, i)
208
			params := append(params, Param{Value: path[i:next]})
209
			if nd, params, found := da.lookup(path[next:], params, idx); found {
210
				return nd, params, true
211
			}
212
		}
213
		if da.bc[idx].IsWildcardParam() {
214
			idx := nextIndex(da.bc[idx].Base(), WildcardCharacter)
215
			params := append(params, Param{Value: path[i:]})
216
			return da.node[da.bc[idx].Base()], params, true
217
		}
218
	}
219
	return nil, nil, false
220
}
221

222
// build builds double-array from records.
223
func (da *doubleArray) build(srcs []*record, idx, depth int, usedBase map[int]struct{}) error {
224
	sort.Stable(recordSlice(srcs))
225
	base, siblings, leaf, err := da.arrange(srcs, idx, depth, usedBase)
226
	if err != nil {
227
		return err
228
	}
229
	if leaf != nil {
230
		nd, err := makeNode(leaf)
231
		if err != nil {
232
			return err
233
		}
234
		da.bc[idx].SetBase(len(da.node))
235
		da.node = append(da.node, nd)
236
	}
237
	for _, sib := range siblings {
238
		da.setCheck(nextIndex(base, sib.c), sib.c)
239
	}
240
	for _, sib := range siblings {
241
		records := srcs[sib.start:sib.end]
242
		switch sib.c {
243
		case ParamCharacter:
244
			for _, r := range records {
245
				next := NextSeparator(r.Key, depth+1)
246
				name := r.Key[depth+1 : next]
247
				r.paramNames = append(r.paramNames, name)
248
				r.Key = r.Key[next:]
249
			}
250
			da.bc[idx].SetSingleParam()
251
			if err := da.build(records, nextIndex(base, sib.c), 0, usedBase); err != nil {
252
				return err
253
			}
254
		case WildcardCharacter:
255
			r := records[0]
256
			name := r.Key[depth+1 : len(r.Key)-1]
257
			r.paramNames = append(r.paramNames, name)
258
			r.Key = ""
259
			da.bc[idx].SetWildcardParam()
260
			if err := da.build(records, nextIndex(base, sib.c), 0, usedBase); err != nil {
261
				return err
262
			}
263
		default:
264
			if err := da.build(records, nextIndex(base, sib.c), depth+1, usedBase); err != nil {
265
				return err
266
			}
267
		}
268
	}
269
	return nil
270
}
271

272
// setBase sets BASE.
273
func (da *doubleArray) setBase(i, base int) {
274
	da.bc[i].SetBase(base)
275
}
276

277
// setCheck sets CHECK.
278
func (da *doubleArray) setCheck(i int, check byte) {
279
	da.bc[i].SetCheck(check)
280
}
281

282
// findEmptyIndex returns an index of unused BASE/CHECK node.
283
func (da *doubleArray) findEmptyIndex(start int) int {
284
	i := start
285
	for ; i < len(da.bc); i++ {
286
		if da.bc[i].IsEmpty() {
287
			break
288
		}
289
	}
290
	return i
291
}
292

293
// findBase returns good BASE.
294
func (da *doubleArray) findBase(siblings []sibling, start int, usedBase map[int]struct{}) (base int) {
295
	for idx, firstChar := start+1, siblings[0].c; ; idx = da.findEmptyIndex(idx + 1) {
296
		base = nextIndex(idx, firstChar)
297
		if _, used := usedBase[base]; used {
298
			continue
299
		}
300
		i := 0
301
		for ; i < len(siblings); i++ {
302
			next := nextIndex(base, siblings[i].c)
303
			if len(da.bc) <= next {
304
				da.bc = append(da.bc, make([]baseCheck, next-len(da.bc)+1)...)
305
			}
306
			if !da.bc[next].IsEmpty() {
307
				break
308
			}
309
		}
310
		if i == len(siblings) {
311
			break
312
		}
313
	}
314
	usedBase[base] = struct{}{}
315
	return base
316
}
317

318
func (da *doubleArray) arrange(records []*record, idx, depth int, usedBase map[int]struct{}) (base int, siblings []sibling, leaf *record, err error) {
319
	siblings, leaf, err = makeSiblings(records, depth)
320
	if err != nil {
321
		return -1, nil, nil, err
322
	}
323
	if len(siblings) < 1 {
324
		return -1, nil, leaf, nil
325
	}
326
	base = da.findBase(siblings, idx, usedBase)
327
	if base > MaxSize {
328
		return -1, nil, nil, fmt.Errorf("denco: too many elements of internal slice")
329
	}
330
	da.setBase(idx, base)
331
	return base, siblings, leaf, err
332
}
333

334
// node represents a node of Double-Array.
335
type node struct {
336
	data interface{}
337

338
	// Names of path parameters.
339
	paramNames []string
340
}
341

342
// makeNode returns a new node from record.
343
func makeNode(r *record) (*node, error) {
344
	dups := make(map[string]bool)
345
	for _, name := range r.paramNames {
346
		if dups[name] {
347
			return nil, fmt.Errorf("denco: path parameter `%v' is duplicated in the key `%v'", name, r.Key)
348
		}
349
		dups[name] = true
350
	}
351
	return &node{data: r.Value, paramNames: r.paramNames}, nil
352
}
353

354
// sibling represents an intermediate data of build for Double-Array.
355
type sibling struct {
356
	// An index of start of duplicated characters.
357
	start int
358

359
	// An index of end of duplicated characters.
360
	end int
361

362
	// A character of sibling.
363
	c byte
364
}
365

366
// nextIndex returns a next index of array of BASE/CHECK.
367
func nextIndex(base int, c byte) int {
368
	return base ^ int(c)
369
}
370

371
// makeSiblings returns slice of sibling.
372
func makeSiblings(records []*record, depth int) (sib []sibling, leaf *record, err error) {
373
	var (
374
		pc byte
375
		n  int
376
	)
377
	for i, r := range records {
378
		if len(r.Key) <= depth {
379
			leaf = r
380
			continue
381
		}
382
		c := r.Key[depth]
383
		switch {
384
		case pc < c:
385
			sib = append(sib, sibling{start: i, c: c})
386
		case pc == c:
387
			continue
388
		default:
389
			return nil, nil, fmt.Errorf("denco: BUG: routing table hasn't been sorted")
390
		}
391
		if n > 0 {
392
			sib[n-1].end = i
393
		}
394
		pc = c
395
		n++
396
	}
397
	if n == 0 {
398
		return nil, leaf, nil
399
	}
400
	sib[n-1].end = len(records)
401
	return sib, leaf, nil
402
}
403

404
// Record represents a record data for router construction.
405
type Record struct {
406
	// Key for router construction.
407
	Key string
408

409
	// Result value for Key.
410
	Value interface{}
411
}
412

413
// NewRecord returns a new Record.
414
func NewRecord(key string, value interface{}) Record {
415
	return Record{
416
		Key:   key,
417
		Value: value,
418
	}
419
}
420

421
// record represents a record that use to build the Double-Array.
422
type record struct {
423
	Record
424
	paramNames []string
425
}
426

427
// makeRecords returns the records that use to build Double-Arrays.
428
func makeRecords(srcs []Record) (statics, params []*record) {
429
	termChar := string(TerminationCharacter)
430
	paramPrefix := string(SeparatorCharacter) + string(ParamCharacter)
431
	wildcardPrefix := string(SeparatorCharacter) + string(WildcardCharacter)
432
	restconfPrefix := string(PathParamCharacter) + string(ParamCharacter)
433
	for _, r := range srcs {
434
		if strings.Contains(r.Key, paramPrefix) || strings.Contains(r.Key, wildcardPrefix) ||strings.Contains(r.Key, restconfPrefix){
435
			r.Key += termChar
436
			params = append(params, &record{Record: r})
437
		} else {
438
			statics = append(statics, &record{Record: r})
439
		}
440
	}
441
	return statics, params
442
}
443

444
// recordSlice represents a slice of Record for sort and implements the sort.Interface.
445
type recordSlice []*record
446

447
// Len implements the sort.Interface.Len.
448
func (rs recordSlice) Len() int {
449
	return len(rs)
450
}
451

452
// Less implements the sort.Interface.Less.
453
func (rs recordSlice) Less(i, j int) bool {
454
	return rs[i].Key < rs[j].Key
455
}
456

457
// Swap implements the sort.Interface.Swap.
458
func (rs recordSlice) Swap(i, j int) {
459
	rs[i], rs[j] = rs[j], rs[i]
460
}
461