src/dma/vendor/github.com/labstack/echo/router.go

   1 package echo
   2
   3 import "net/http"
   4
   5 type (
   6         // Router is the registry of all registered routes for an `Echo` instance for
   7         // request matching and URL path parameter parsing.
   8         Router struct {
   9                 tree   *node
  10                 routes map[string]*Route
  11                 echo   *Echo
  12         }
  13         node struct {
  14                 kind          kind
  15                 label         byte
  16                 prefix        string
  17                 parent        *node
  18                 children      children
  19                 ppath         string
  20                 pnames        []string
  21                 methodHandler *methodHandler
  22         }
  23         kind          uint8
  24         children      []*node
  25         methodHandler struct {
  26                 connect  HandlerFunc
  27                 delete   HandlerFunc
  28                 get      HandlerFunc
  29                 head     HandlerFunc
  30                 options  HandlerFunc
  31                 patch    HandlerFunc
  32                 post     HandlerFunc
  33                 propfind HandlerFunc
  34                 put      HandlerFunc
  35                 trace    HandlerFunc
  36         }
  37 )
  38
  39 const (
  40         skind kind = iota
  41         pkind
  42         akind
  43 )
  44
  45 // NewRouter returns a new Router instance.
  46 func NewRouter(e *Echo) *Router {
  47         return &Router{
  48                 tree: &node{
  49                         methodHandler: new(methodHandler),
  50                 },
  51                 routes: map[string]*Route{},
  52                 echo:   e,
  53         }
  54 }
  55
  56 // Add registers a new route for method and path with matching handler.
  57 func (r *Router) Add(method, path string, h HandlerFunc) {
  58         // Validate path
  59         if path == "" {
  60                 panic("echo: path cannot be empty")
  61         }
  62         if path[0] != '/' {
  63                 path = "/" + path
  64         }
  65         pnames := []string{} // Param names
  66         ppath := path        // Pristine path
  67
  68         for i, l := 0, len(path); i < l; i++ {
  69                 if path[i] == ':' {
  70                         j := i + 1
  71
  72                         r.insert(method, path[:i], nil, skind, "", nil)
  73                         for ; i < l && path[i] != '/'; i++ {
  74                         }
  75
  76                         pnames = append(pnames, path[j:i])
  77                         path = path[:j] + path[i:]
  78                         i, l = j, len(path)
  79
  80                         if i == l {
  81                                 r.insert(method, path[:i], h, pkind, ppath, pnames)
  82                                 return
  83                         }
  84                         r.insert(method, path[:i], nil, pkind, "", nil)
  85                 } else if path[i] == '*' {
  86                         r.insert(method, path[:i], nil, skind, "", nil)
  87                         pnames = append(pnames, "*")
  88                         r.insert(method, path[:i+1], h, akind, ppath, pnames)
  89                         return
  90                 }
  91         }
  92
  93         r.insert(method, path, h, skind, ppath, pnames)
  94 }
  95
  96 func (r *Router) insert(method, path string, h HandlerFunc, t kind, ppath string, pnames []string) {
  97         // Adjust max param
  98         l := len(pnames)
  99         if *r.echo.maxParam < l {
 100                 *r.echo.maxParam = l
 101         }
 102
 103         cn := r.tree // Current node as root
 104         if cn == nil {
 105                 panic("echo: invalid method")
 106         }
 107         search := path
 108
 109         for {
 110                 sl := len(search)
 111                 pl := len(cn.prefix)
 112                 l := 0
 113
 114                 // LCP
 115                 max := pl
 116                 if sl < max {
 117                         max = sl
 118                 }
 119                 for ; l < max && search[l] == cn.prefix[l]; l++ {
 120                 }
 121
 122                 if l == 0 {
 123                         // At root node
 124                         cn.label = search[0]
 125                         cn.prefix = search
 126                         if h != nil {
 127                                 cn.kind = t
 128                                 cn.addHandler(method, h)
 129                                 cn.ppath = ppath
 130                                 cn.pnames = pnames
 131                         }
 132                 } else if l < pl {
 133                         // Split node
 134                         n := newNode(cn.kind, cn.prefix[l:], cn, cn.children, cn.methodHandler, cn.ppath, cn.pnames)
 135
 136                         // Reset parent node
 137                         cn.kind = skind
 138                         cn.label = cn.prefix[0]
 139                         cn.prefix = cn.prefix[:l]
 140                         cn.children = nil
 141                         cn.methodHandler = new(methodHandler)
 142                         cn.ppath = ""
 143                         cn.pnames = nil
 144
 145                         cn.addChild(n)
 146
 147                         if l == sl {
 148                                 // At parent node
 149                                 cn.kind = t
 150                                 cn.addHandler(method, h)
 151                                 cn.ppath = ppath
 152                                 cn.pnames = pnames
 153                         } else {
 154                                 // Create child node
 155                                 n = newNode(t, search[l:], cn, nil, new(methodHandler), ppath, pnames)
 156                                 n.addHandler(method, h)
 157                                 cn.addChild(n)
 158                         }
 159                 } else if l < sl {
 160                         search = search[l:]
 161                         c := cn.findChildWithLabel(search[0])
 162                         if c != nil {
 163                                 // Go deeper
 164                                 cn = c
 165                                 continue
 166                         }
 167                         // Create child node
 168                         n := newNode(t, search, cn, nil, new(methodHandler), ppath, pnames)
 169                         n.addHandler(method, h)
 170                         cn.addChild(n)
 171                 } else {
 172                         // Node already exists
 173                         if h != nil {
 174                                 cn.addHandler(method, h)
 175                                 cn.ppath = ppath
 176                                 if len(cn.pnames) == 0 { // Issue #729
 177                                         cn.pnames = pnames
 178                                 }
 179                         }
 180                 }
 181                 return
 182         }
 183 }
 184
 185 func newNode(t kind, pre string, p *node, c children, mh *methodHandler, ppath string, pnames []string) *node {
 186         return &node{
 187                 kind:          t,
 188                 label:         pre[0],
 189                 prefix:        pre,
 190                 parent:        p,
 191                 children:      c,
 192                 ppath:         ppath,
 193                 pnames:        pnames,
 194                 methodHandler: mh,
 195         }
 196 }
 197
 198 func (n *node) addChild(c *node) {
 199         n.children = append(n.children, c)
 200 }
 201
 202 func (n *node) findChild(l byte, t kind) *node {
 203         for _, c := range n.children {
 204                 if c.label == l && c.kind == t {
 205                         return c
 206                 }
 207         }
 208         return nil
 209 }
 210
 211 func (n *node) findChildWithLabel(l byte) *node {
 212         for _, c := range n.children {
 213                 if c.label == l {
 214                         return c
 215                 }
 216         }
 217         return nil
 218 }
 219
 220 func (n *node) findChildByKind(t kind) *node {
 221         for _, c := range n.children {
 222                 if c.kind == t {
 223                         return c
 224                 }
 225         }
 226         return nil
 227 }
 228
 229 func (n *node) addHandler(method string, h HandlerFunc) {
 230         switch method {
 231         case http.MethodConnect:
 232                 n.methodHandler.connect = h
 233         case http.MethodDelete:
 234                 n.methodHandler.delete = h
 235         case http.MethodGet:
 236                 n.methodHandler.get = h
 237         case http.MethodHead:
 238                 n.methodHandler.head = h
 239         case http.MethodOptions:
 240                 n.methodHandler.options = h
 241         case http.MethodPatch:
 242                 n.methodHandler.patch = h
 243         case http.MethodPost:
 244                 n.methodHandler.post = h
 245         case PROPFIND:
 246                 n.methodHandler.propfind = h
 247         case http.MethodPut:
 248                 n.methodHandler.put = h
 249         case http.MethodTrace:
 250                 n.methodHandler.trace = h
 251         }
 252 }
 253
 254 func (n *node) findHandler(method string) HandlerFunc {
 255         switch method {
 256         case http.MethodConnect:
 257                 return n.methodHandler.connect
 258         case http.MethodDelete:
 259                 return n.methodHandler.delete
 260         case http.MethodGet:
 261                 return n.methodHandler.get
 262         case http.MethodHead:
 263                 return n.methodHandler.head
 264         case http.MethodOptions:
 265                 return n.methodHandler.options
 266         case http.MethodPatch:
 267                 return n.methodHandler.patch
 268         case http.MethodPost:
 269                 return n.methodHandler.post
 270         case PROPFIND:
 271                 return n.methodHandler.propfind
 272         case http.MethodPut:
 273                 return n.methodHandler.put
 274         case http.MethodTrace:
 275                 return n.methodHandler.trace
 276         default:
 277                 return nil
 278         }
 279 }
 280
 281 func (n *node) checkMethodNotAllowed() HandlerFunc {
 282         for _, m := range methods {
 283                 if h := n.findHandler(m); h != nil {
 284                         return MethodNotAllowedHandler
 285                 }
 286         }
 287         return NotFoundHandler
 288 }
 289
 290 // Find lookup a handler registered for method and path. It also parses URL for path
 291 // parameters and load them into context.
 292 //
 293 // For performance:
 294 //
 295 // - Get context from `Echo#AcquireContext()`
 296 // - Reset it `Context#Reset()`
 297 // - Return it `Echo#ReleaseContext()`.
 298 func (r *Router) Find(method, path string, c Context) {
 299         ctx := c.(*context)
 300         ctx.path = path
 301         cn := r.tree // Current node as root
 302
 303         var (
 304                 search  = path
 305                 child   *node         // Child node
 306                 n       int           // Param counter
 307                 nk      kind          // Next kind
 308                 nn      *node         // Next node
 309                 ns      string        // Next search
 310                 pvalues = ctx.pvalues // Use the internal slice so the interface can keep the illusion of a dynamic slice
 311         )
 312
 313         // Search order static > param > any
 314         for {
 315                 if search == "" {
 316                         break
 317                 }
 318
 319                 pl := 0 // Prefix length
 320                 l := 0  // LCP length
 321
 322                 if cn.label != ':' {
 323                         sl := len(search)
 324                         pl = len(cn.prefix)
 325
 326                         // LCP
 327                         max := pl
 328                         if sl < max {
 329                                 max = sl
 330                         }
 331                         for ; l < max && search[l] == cn.prefix[l]; l++ {
 332                         }
 333                 }
 334
 335                 if l == pl {
 336                         // Continue search
 337                         search = search[l:]
 338                 } else {
 339                         cn = nn
 340                         search = ns
 341                         if nk == pkind {
 342                                 goto Param
 343                         } else if nk == akind {
 344                                 goto Any
 345                         }
 346                         // Not found
 347                         return
 348                 }
 349
 350                 if search == "" {
 351                         break
 352                 }
 353
 354                 // Static node
 355                 if child = cn.findChild(search[0], skind); child != nil {
 356                         // Save next
 357                         if cn.prefix[len(cn.prefix)-1] == '/' { // Issue #623
 358                                 nk = pkind
 359                                 nn = cn
 360                                 ns = search
 361                         }
 362                         cn = child
 363                         continue
 364                 }
 365
 366                 // Param node
 367         Param:
 368                 if child = cn.findChildByKind(pkind); child != nil {
 369                         // Issue #378
 370                         if len(pvalues) == n {
 371                                 continue
 372                         }
 373
 374                         // Save next
 375                         if cn.prefix[len(cn.prefix)-1] == '/' { // Issue #623
 376                                 nk = akind
 377                                 nn = cn
 378                                 ns = search
 379                         }
 380
 381                         cn = child
 382                         i, l := 0, len(search)
 383                         for ; i < l && search[i] != '/'; i++ {
 384                         }
 385                         pvalues[n] = search[:i]
 386                         n++
 387                         search = search[i:]
 388                         continue
 389                 }
 390
 391                 // Any node
 392         Any:
 393                 if cn = cn.findChildByKind(akind); cn == nil {
 394                         if nn != nil {
 395                                 cn = nn
 396                                 nn = cn.parent // Next (Issue #954)
 397                                 search = ns
 398                                 if nk == pkind {
 399                                         goto Param
 400                                 } else if nk == akind {
 401                                         goto Any
 402                                 }
 403                         }
 404                         // Not found
 405                         return
 406                 }
 407                 pvalues[len(cn.pnames)-1] = search
 408                 break
 409         }
 410
 411         ctx.handler = cn.findHandler(method)
 412         ctx.path = cn.ppath
 413         ctx.pnames = cn.pnames
 414
 415         // NOTE: Slow zone...
 416         if ctx.handler == nil {
 417                 ctx.handler = cn.checkMethodNotAllowed()
 418
 419                 // Dig further for any, might have an empty value for *, e.g.
 420                 // serving a directory. Issue #207.
 421                 if cn = cn.findChildByKind(akind); cn == nil {
 422                         return
 423                 }
 424                 if h := cn.findHandler(method); h != nil {
 425                         ctx.handler = h
 426                 } else {
 427                         ctx.handler = cn.checkMethodNotAllowed()
 428                 }
 429                 ctx.path = cn.ppath
 430                 ctx.pnames = cn.pnames
 431                 pvalues[len(cn.pnames)-1] = ""
 432         }
 433
 434         return
 435 }