router.go

Documentation: github.com/go-openapi/runtime/middleware/denco

     1  // Package denco provides fast URL router.
     2  package denco
     3  
     4  import (
     5  	"errors"
     6  	"fmt"
     7  	"sort"
     8  	"strings"
     9  )
    10  
    11  const (
    12  	// ParamCharacter is a special character for path parameter.
    13  	ParamCharacter = ':'
    14  
    15  	// WildcardCharacter is a special character for wildcard path parameter.
    16  	WildcardCharacter = '*'
    17  
    18  	// TerminationCharacter is a special character for end of path.
    19  	TerminationCharacter = '#'
    20  
    21  	// SeparatorCharacter separates path segments.
    22  	SeparatorCharacter = '/'
    23  
    24  	// PathParamCharacter indicates a RESTCONF path param
    25  	PathParamCharacter = '='
    26  
    27  	// MaxSize is max size of records and internal slice.
    28  	MaxSize = (1 << 22) - 1
    29  )
    30  
    31  // Router represents a URL router.
    32  type Router struct {
    33  	param *doubleArray
    34  	// SizeHint expects the maximum number of path parameters in records to Build.
    35  	// SizeHint will be used to determine the capacity of the memory to allocate.
    36  	// By default, SizeHint will be determined from given records to Build.
    37  	SizeHint int
    38  
    39  	static map[string]interface{}
    40  }
    41  
    42  // New returns a new Router.
    43  func New() *Router {
    44  	return &Router{
    45  		SizeHint: -1,
    46  		static:   make(map[string]interface{}),
    47  		param:    newDoubleArray(),
    48  	}
    49  }
    50  
    51  // Lookup returns data and path parameters that associated with path.
    52  // params is a slice of the Param that arranged in the order in which parameters appeared.
    53  // 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"}].
    54  func (rt *Router) Lookup(path string) (data interface{}, params Params, found bool) {
    55  	if data, found = rt.static[path]; found {
    56  		return data, nil, true
    57  	}
    58  	if len(rt.param.node) == 1 {
    59  		return nil, nil, false
    60  	}
    61  	nd, params, found := rt.param.lookup(path, make([]Param, 0, rt.SizeHint), 1)
    62  	if !found {
    63  		return nil, nil, false
    64  	}
    65  	for i := 0; i < len(params); i++ {
    66  		params[i].Name = nd.paramNames[i]
    67  	}
    68  	return nd.data, params, true
    69  }
    70  
    71  // Build builds URL router from records.
    72  func (rt *Router) Build(records []Record) error {
    73  	statics, params := makeRecords(records)
    74  	if len(params) > MaxSize {
    75  		return errors.New("denco: too many records")
    76  	}
    77  	if rt.SizeHint < 0 {
    78  		rt.SizeHint = 0
    79  		for _, p := range params {
    80  			size := 0
    81  			for _, k := range p.Key {
    82  				if k == ParamCharacter || k == WildcardCharacter {
    83  					size++
    84  				}
    85  			}
    86  			if size > rt.SizeHint {
    87  				rt.SizeHint = size
    88  			}
    89  		}
    90  	}
    91  	for _, r := range statics {
    92  		rt.static[r.Key] = r.Value
    93  	}
    94  	if err := rt.param.build(params, 1, 0, make(map[int]struct{})); err != nil {
    95  		return err
    96  	}
    97  	return nil
    98  }
    99  
   100  // Param represents name and value of path parameter.
   101  type Param struct {
   102  	Name  string
   103  	Value string
   104  }
   105  
   106  // Params represents the name and value of path parameters.
   107  type Params []Param
   108  
   109  // Get gets the first value associated with the given name.
   110  // If there are no values associated with the key, Get returns "".
   111  func (ps Params) Get(name string) string {
   112  	for _, p := range ps {
   113  		if p.Name == name {
   114  			return p.Value
   115  		}
   116  	}
   117  	return ""
   118  }
   119  
   120  type doubleArray struct {
   121  	bc   []baseCheck
   122  	node []*node
   123  }
   124  
   125  func newDoubleArray() *doubleArray {
   126  	return &doubleArray{
   127  		bc:   []baseCheck{0},
   128  		node: []*node{nil}, // A start index is adjusting to 1 because 0 will be used as a mark of non-existent node.
   129  	}
   130  }
   131  
   132  // baseCheck contains BASE, CHECK and Extra flags.
   133  // From the top, 22bits of BASE, 2bits of Extra flags and 8bits of CHECK.
   134  //
   135  //	BASE (22bit) | Extra flags (2bit) | CHECK (8bit)
   136  //
   137  // |----------------------|--|--------|
   138  // 32                    10  8         0
   139  type baseCheck uint32
   140  
   141  func (bc baseCheck) Base() int {
   142  	return int(bc >> 10)
   143  }
   144  
   145  func (bc *baseCheck) SetBase(base int) {
   146  	*bc |= baseCheck(base) << 10
   147  }
   148  
   149  func (bc baseCheck) Check() byte {
   150  	return byte(bc)
   151  }
   152  
   153  func (bc *baseCheck) SetCheck(check byte) {
   154  	*bc |= baseCheck(check)
   155  }
   156  
   157  func (bc baseCheck) IsEmpty() bool {
   158  	return bc&0xfffffcff == 0
   159  }
   160  
   161  func (bc baseCheck) IsSingleParam() bool {
   162  	return bc&paramTypeSingle == paramTypeSingle
   163  }
   164  
   165  func (bc baseCheck) IsWildcardParam() bool {
   166  	return bc&paramTypeWildcard == paramTypeWildcard
   167  }
   168  
   169  func (bc baseCheck) IsAnyParam() bool {
   170  	return bc&paramTypeAny != 0
   171  }
   172  
   173  func (bc *baseCheck) SetSingleParam() {
   174  	*bc |= (1 << 8)
   175  }
   176  
   177  func (bc *baseCheck) SetWildcardParam() {
   178  	*bc |= (1 << 9)
   179  }
   180  
   181  const (
   182  	paramTypeSingle   = 0x0100
   183  	paramTypeWildcard = 0x0200
   184  	paramTypeAny      = 0x0300
   185  )
   186  
   187  func (da *doubleArray) lookup(path string, params []Param, idx int) (*node, []Param, bool) {
   188  	indices := make([]uint64, 0, 1)
   189  	for i := 0; i < len(path); i++ {
   190  		if da.bc[idx].IsAnyParam() {
   191  			indices = append(indices, (uint64(i)<<32)|(uint64(idx)&0xffffffff))
   192  		}
   193  		c := path[i]
   194  		if idx = nextIndex(da.bc[idx].Base(), c); idx >= len(da.bc) || da.bc[idx].Check() != c {
   195  			goto BACKTRACKING
   196  		}
   197  	}
   198  	if next := nextIndex(da.bc[idx].Base(), TerminationCharacter); next < len(da.bc) && da.bc[next].Check() == TerminationCharacter {
   199  		return da.node[da.bc[next].Base()], params, true
   200  	}
   201  
   202  BACKTRACKING:
   203  	for j := len(indices) - 1; j >= 0; j-- {
   204  		i, idx := int(indices[j]>>32), int(indices[j]&0xffffffff)
   205  		if da.bc[idx].IsSingleParam() {
   206  			nextIdx := nextIndex(da.bc[idx].Base(), ParamCharacter)
   207  			if nextIdx >= len(da.bc) {
   208  				break
   209  			}
   210  
   211  			next := NextSeparator(path, i)
   212  			nextParams := params
   213  			nextParams = append(nextParams, Param{Value: path[i:next]})
   214  			if nd, nextNextParams, found := da.lookup(path[next:], nextParams, nextIdx); found {
   215  				return nd, nextNextParams, true
   216  			}
   217  		}
   218  
   219  		if da.bc[idx].IsWildcardParam() {
   220  			nextIdx := nextIndex(da.bc[idx].Base(), WildcardCharacter)
   221  			nextParams := params
   222  			nextParams = append(nextParams, Param{Value: path[i:]})
   223  			return da.node[da.bc[nextIdx].Base()], nextParams, true
   224  		}
   225  	}
   226  	return nil, nil, false
   227  }
   228  
   229  // build builds double-array from records.
   230  func (da *doubleArray) build(srcs []*record, idx, depth int, usedBase map[int]struct{}) error {
   231  	sort.Stable(recordSlice(srcs))
   232  	base, siblings, leaf, err := da.arrange(srcs, idx, depth, usedBase)
   233  	if err != nil {
   234  		return err
   235  	}
   236  	if leaf != nil {
   237  		nd, err := makeNode(leaf)
   238  		if err != nil {
   239  			return err
   240  		}
   241  		da.bc[idx].SetBase(len(da.node))
   242  		da.node = append(da.node, nd)
   243  	}
   244  	for _, sib := range siblings {
   245  		da.setCheck(nextIndex(base, sib.c), sib.c)
   246  	}
   247  	for _, sib := range siblings {
   248  		records := srcs[sib.start:sib.end]
   249  		switch sib.c {
   250  		case ParamCharacter:
   251  			for _, r := range records {
   252  				next := NextSeparator(r.Key, depth+1)
   253  				name := r.Key[depth+1 : next]
   254  				r.paramNames = append(r.paramNames, name)
   255  				r.Key = r.Key[next:]
   256  			}
   257  			da.bc[idx].SetSingleParam()
   258  			if err := da.build(records, nextIndex(base, sib.c), 0, usedBase); err != nil {
   259  				return err
   260  			}
   261  		case WildcardCharacter:
   262  			r := records[0]
   263  			name := r.Key[depth+1 : len(r.Key)-1]
   264  			r.paramNames = append(r.paramNames, name)
   265  			r.Key = ""
   266  			da.bc[idx].SetWildcardParam()
   267  			if err := da.build(records, nextIndex(base, sib.c), 0, usedBase); err != nil {
   268  				return err
   269  			}
   270  		default:
   271  			if err := da.build(records, nextIndex(base, sib.c), depth+1, usedBase); err != nil {
   272  				return err
   273  			}
   274  		}
   275  	}
   276  	return nil
   277  }
   278  
   279  // setBase sets BASE.
   280  func (da *doubleArray) setBase(i, base int) {
   281  	da.bc[i].SetBase(base)
   282  }
   283  
   284  // setCheck sets CHECK.
   285  func (da *doubleArray) setCheck(i int, check byte) {
   286  	da.bc[i].SetCheck(check)
   287  }
   288  
   289  // findEmptyIndex returns an index of unused BASE/CHECK node.
   290  func (da *doubleArray) findEmptyIndex(start int) int {
   291  	i := start
   292  	for ; i < len(da.bc); i++ {
   293  		if da.bc[i].IsEmpty() {
   294  			break
   295  		}
   296  	}
   297  	return i
   298  }
   299  
   300  // findBase returns good BASE.
   301  func (da *doubleArray) findBase(siblings []sibling, start int, usedBase map[int]struct{}) (base int) {
   302  	for idx, firstChar := start+1, siblings[0].c; ; idx = da.findEmptyIndex(idx + 1) {
   303  		base = nextIndex(idx, firstChar)
   304  		if _, used := usedBase[base]; used {
   305  			continue
   306  		}
   307  		i := 0
   308  		for ; i < len(siblings); i++ {
   309  			next := nextIndex(base, siblings[i].c)
   310  			if len(da.bc) <= next {
   311  				da.bc = append(da.bc, make([]baseCheck, next-len(da.bc)+1)...)
   312  			}
   313  			if !da.bc[next].IsEmpty() {
   314  				break
   315  			}
   316  		}
   317  		if i == len(siblings) {
   318  			break
   319  		}
   320  	}
   321  	usedBase[base] = struct{}{}
   322  	return base
   323  }
   324  
   325  func (da *doubleArray) arrange(records []*record, idx, depth int, usedBase map[int]struct{}) (base int, siblings []sibling, leaf *record, err error) {
   326  	siblings, leaf, err = makeSiblings(records, depth)
   327  	if err != nil {
   328  		return -1, nil, nil, err
   329  	}
   330  	if len(siblings) < 1 {
   331  		return -1, nil, leaf, nil
   332  	}
   333  	base = da.findBase(siblings, idx, usedBase)
   334  	if base > MaxSize {
   335  		return -1, nil, nil, errors.New("denco: too many elements of internal slice")
   336  	}
   337  	da.setBase(idx, base)
   338  	return base, siblings, leaf, err
   339  }
   340  
   341  // node represents a node of Double-Array.
   342  type node struct {
   343  	data interface{}
   344  
   345  	// Names of path parameters.
   346  	paramNames []string
   347  }
   348  
   349  // makeNode returns a new node from record.
   350  func makeNode(r *record) (*node, error) {
   351  	dups := make(map[string]bool)
   352  	for _, name := range r.paramNames {
   353  		if dups[name] {
   354  			return nil, fmt.Errorf("denco: path parameter `%v' is duplicated in the key `%v'", name, r.Key)
   355  		}
   356  		dups[name] = true
   357  	}
   358  	return &node{data: r.Value, paramNames: r.paramNames}, nil
   359  }
   360  
   361  // sibling represents an intermediate data of build for Double-Array.
   362  type sibling struct {
   363  	// An index of start of duplicated characters.
   364  	start int
   365  
   366  	// An index of end of duplicated characters.
   367  	end int
   368  
   369  	// A character of sibling.
   370  	c byte
   371  }
   372  
   373  // nextIndex returns a next index of array of BASE/CHECK.
   374  func nextIndex(base int, c byte) int {
   375  	return base ^ int(c)
   376  }
   377  
   378  // makeSiblings returns slice of sibling.
   379  func makeSiblings(records []*record, depth int) (sib []sibling, leaf *record, err error) {
   380  	var (
   381  		pc byte
   382  		n  int
   383  	)
   384  	for i, r := range records {
   385  		if len(r.Key) <= depth {
   386  			leaf = r
   387  			continue
   388  		}
   389  		c := r.Key[depth]
   390  		switch {
   391  		case pc < c:
   392  			sib = append(sib, sibling{start: i, c: c})
   393  		case pc == c:
   394  			continue
   395  		default:
   396  			return nil, nil, errors.New("denco: BUG: routing table hasn't been sorted")
   397  		}
   398  		if n > 0 {
   399  			sib[n-1].end = i
   400  		}
   401  		pc = c
   402  		n++
   403  	}
   404  	if n == 0 {
   405  		return nil, leaf, nil
   406  	}
   407  	sib[n-1].end = len(records)
   408  	return sib, leaf, nil
   409  }
   410  
   411  // Record represents a record data for router construction.
   412  type Record struct {
   413  	// Key for router construction.
   414  	Key string
   415  
   416  	// Result value for Key.
   417  	Value interface{}
   418  }
   419  
   420  // NewRecord returns a new Record.
   421  func NewRecord(key string, value interface{}) Record {
   422  	return Record{
   423  		Key:   key,
   424  		Value: value,
   425  	}
   426  }
   427  
   428  // record represents a record that use to build the Double-Array.
   429  type record struct {
   430  	Record
   431  	paramNames []string
   432  }
   433  
   434  // makeRecords returns the records that use to build Double-Arrays.
   435  func makeRecords(srcs []Record) (statics, params []*record) {
   436  	termChar := string(TerminationCharacter)
   437  	paramPrefix := string(SeparatorCharacter) + string(ParamCharacter)
   438  	wildcardPrefix := string(SeparatorCharacter) + string(WildcardCharacter)
   439  	restconfPrefix := string(PathParamCharacter) + string(ParamCharacter)
   440  	for _, r := range srcs {
   441  		if strings.Contains(r.Key, paramPrefix) || strings.Contains(r.Key, wildcardPrefix) || strings.Contains(r.Key, restconfPrefix) {
   442  			r.Key += termChar
   443  			params = append(params, &record{Record: r})
   444  		} else {
   445  			statics = append(statics, &record{Record: r})
   446  		}
   447  	}
   448  	return statics, params
   449  }
   450  
   451  // recordSlice represents a slice of Record for sort and implements the sort.Interface.
   452  type recordSlice []*record
   453  
   454  // Len implements the sort.Interface.Len.
   455  func (rs recordSlice) Len() int {
   456  	return len(rs)
   457  }
   458  
   459  // Less implements the sort.Interface.Less.
   460  func (rs recordSlice) Less(i, j int) bool {
   461  	return rs[i].Key < rs[j].Key
   462  }
   463  
   464  // Swap implements the sort.Interface.Swap.
   465  func (rs recordSlice) Swap(i, j int) {
   466  	rs[i], rs[j] = rs[j], rs[i]
   467  }
   468
View as plain text