1package echo 2 3import ( 4 "net/http" 5) 6 7type ( 8 // Router is the registry of all registered routes for an `Echo` instance for 9 // request matching and URL path parameter parsing. 10 Router struct { 11 tree *node 12 routes map[string]*Route 13 echo *Echo 14 } 15 node struct { 16 kind kind 17 label byte 18 prefix string 19 parent *node 20 staticChildren children 21 ppath string 22 pnames []string 23 methodHandler *methodHandler 24 paramChild *node 25 anyChild *node 26 // isLeaf indicates that node does not have child routes 27 isLeaf bool 28 // isHandler indicates that node has at least one handler registered to it 29 isHandler bool 30 } 31 kind uint8 32 children []*node 33 methodHandler struct { 34 connect HandlerFunc 35 delete HandlerFunc 36 get HandlerFunc 37 head HandlerFunc 38 options HandlerFunc 39 patch HandlerFunc 40 post HandlerFunc 41 propfind HandlerFunc 42 put HandlerFunc 43 trace HandlerFunc 44 report HandlerFunc 45 } 46) 47 48const ( 49 staticKind kind = iota 50 paramKind 51 anyKind 52 53 paramLabel = byte(':') 54 anyLabel = byte('*') 55) 56 57func (m *methodHandler) isHandler() bool { 58 return m.connect != nil || 59 m.delete != nil || 60 m.get != nil || 61 m.head != nil || 62 m.options != nil || 63 m.patch != nil || 64 m.post != nil || 65 m.propfind != nil || 66 m.put != nil || 67 m.trace != nil || 68 m.report != nil 69} 70 71// NewRouter returns a new Router instance. 72func NewRouter(e *Echo) *Router { 73 return &Router{ 74 tree: &node{ 75 methodHandler: new(methodHandler), 76 }, 77 routes: map[string]*Route{}, 78 echo: e, 79 } 80} 81 82// Add registers a new route for method and path with matching handler. 83func (r *Router) Add(method, path string, h HandlerFunc) { 84 // Validate path 85 if path == "" { 86 path = "/" 87 } 88 if path[0] != '/' { 89 path = "/" + path 90 } 91 pnames := []string{} // Param names 92 ppath := path // Pristine path 93 94 if h == nil && r.echo.Logger != nil { 95 // FIXME: in future we should return error 96 r.echo.Logger.Errorf("Adding route without handler function: %v:%v", method, path) 97 } 98 99 for i, lcpIndex := 0, len(path); i < lcpIndex; i++ { 100 if path[i] == ':' { 101 j := i + 1 102 103 r.insert(method, path[:i], nil, staticKind, "", nil) 104 for ; i < lcpIndex && path[i] != '/'; i++ { 105 } 106 107 pnames = append(pnames, path[j:i]) 108 path = path[:j] + path[i:] 109 i, lcpIndex = j, len(path) 110 111 if i == lcpIndex { 112 // path node is last fragment of route path. ie. `/users/:id` 113 r.insert(method, path[:i], h, paramKind, ppath, pnames) 114 } else { 115 r.insert(method, path[:i], nil, paramKind, "", nil) 116 } 117 } else if path[i] == '*' { 118 r.insert(method, path[:i], nil, staticKind, "", nil) 119 pnames = append(pnames, "*") 120 r.insert(method, path[:i+1], h, anyKind, ppath, pnames) 121 } 122 } 123 124 r.insert(method, path, h, staticKind, ppath, pnames) 125} 126 127func (r *Router) insert(method, path string, h HandlerFunc, t kind, ppath string, pnames []string) { 128 // Adjust max param 129 paramLen := len(pnames) 130 if *r.echo.maxParam < paramLen { 131 *r.echo.maxParam = paramLen 132 } 133 134 currentNode := r.tree // Current node as root 135 if currentNode == nil { 136 panic("echo: invalid method") 137 } 138 search := path 139 140 for { 141 searchLen := len(search) 142 prefixLen := len(currentNode.prefix) 143 lcpLen := 0 144 145 // LCP - Longest Common Prefix (https://en.wikipedia.org/wiki/LCP_array) 146 max := prefixLen 147 if searchLen < max { 148 max = searchLen 149 } 150 for ; lcpLen < max && search[lcpLen] == currentNode.prefix[lcpLen]; lcpLen++ { 151 } 152 153 if lcpLen == 0 { 154 // At root node 155 currentNode.label = search[0] 156 currentNode.prefix = search 157 if h != nil { 158 currentNode.kind = t 159 currentNode.addHandler(method, h) 160 currentNode.ppath = ppath 161 currentNode.pnames = pnames 162 } 163 currentNode.isLeaf = currentNode.staticChildren == nil && currentNode.paramChild == nil && currentNode.anyChild == nil 164 } else if lcpLen < prefixLen { 165 // Split node 166 n := newNode( 167 currentNode.kind, 168 currentNode.prefix[lcpLen:], 169 currentNode, 170 currentNode.staticChildren, 171 currentNode.methodHandler, 172 currentNode.ppath, 173 currentNode.pnames, 174 currentNode.paramChild, 175 currentNode.anyChild, 176 ) 177 // Update parent path for all children to new node 178 for _, child := range currentNode.staticChildren { 179 child.parent = n 180 } 181 if currentNode.paramChild != nil { 182 currentNode.paramChild.parent = n 183 } 184 if currentNode.anyChild != nil { 185 currentNode.anyChild.parent = n 186 } 187 188 // Reset parent node 189 currentNode.kind = staticKind 190 currentNode.label = currentNode.prefix[0] 191 currentNode.prefix = currentNode.prefix[:lcpLen] 192 currentNode.staticChildren = nil 193 currentNode.methodHandler = new(methodHandler) 194 currentNode.ppath = "" 195 currentNode.pnames = nil 196 currentNode.paramChild = nil 197 currentNode.anyChild = nil 198 currentNode.isLeaf = false 199 currentNode.isHandler = false 200 201 // Only Static children could reach here 202 currentNode.addStaticChild(n) 203 204 if lcpLen == searchLen { 205 // At parent node 206 currentNode.kind = t 207 currentNode.addHandler(method, h) 208 currentNode.ppath = ppath 209 currentNode.pnames = pnames 210 } else { 211 // Create child node 212 n = newNode(t, search[lcpLen:], currentNode, nil, new(methodHandler), ppath, pnames, nil, nil) 213 n.addHandler(method, h) 214 // Only Static children could reach here 215 currentNode.addStaticChild(n) 216 } 217 currentNode.isLeaf = currentNode.staticChildren == nil && currentNode.paramChild == nil && currentNode.anyChild == nil 218 } else if lcpLen < searchLen { 219 search = search[lcpLen:] 220 c := currentNode.findChildWithLabel(search[0]) 221 if c != nil { 222 // Go deeper 223 currentNode = c 224 continue 225 } 226 // Create child node 227 n := newNode(t, search, currentNode, nil, new(methodHandler), ppath, pnames, nil, nil) 228 n.addHandler(method, h) 229 switch t { 230 case staticKind: 231 currentNode.addStaticChild(n) 232 case paramKind: 233 currentNode.paramChild = n 234 case anyKind: 235 currentNode.anyChild = n 236 } 237 currentNode.isLeaf = currentNode.staticChildren == nil && currentNode.paramChild == nil && currentNode.anyChild == nil 238 } else { 239 // Node already exists 240 if h != nil { 241 currentNode.addHandler(method, h) 242 currentNode.ppath = ppath 243 if len(currentNode.pnames) == 0 { // Issue #729 244 currentNode.pnames = pnames 245 } 246 } 247 } 248 return 249 } 250} 251 252func newNode(t kind, pre string, p *node, sc children, mh *methodHandler, ppath string, pnames []string, paramChildren, anyChildren *node) *node { 253 return &node{ 254 kind: t, 255 label: pre[0], 256 prefix: pre, 257 parent: p, 258 staticChildren: sc, 259 ppath: ppath, 260 pnames: pnames, 261 methodHandler: mh, 262 paramChild: paramChildren, 263 anyChild: anyChildren, 264 isLeaf: sc == nil && paramChildren == nil && anyChildren == nil, 265 isHandler: mh.isHandler(), 266 } 267} 268 269func (n *node) addStaticChild(c *node) { 270 n.staticChildren = append(n.staticChildren, c) 271} 272 273func (n *node) findStaticChild(l byte) *node { 274 for _, c := range n.staticChildren { 275 if c.label == l { 276 return c 277 } 278 } 279 return nil 280} 281 282func (n *node) findChildWithLabel(l byte) *node { 283 for _, c := range n.staticChildren { 284 if c.label == l { 285 return c 286 } 287 } 288 if l == paramLabel { 289 return n.paramChild 290 } 291 if l == anyLabel { 292 return n.anyChild 293 } 294 return nil 295} 296 297func (n *node) addHandler(method string, h HandlerFunc) { 298 switch method { 299 case http.MethodConnect: 300 n.methodHandler.connect = h 301 case http.MethodDelete: 302 n.methodHandler.delete = h 303 case http.MethodGet: 304 n.methodHandler.get = h 305 case http.MethodHead: 306 n.methodHandler.head = h 307 case http.MethodOptions: 308 n.methodHandler.options = h 309 case http.MethodPatch: 310 n.methodHandler.patch = h 311 case http.MethodPost: 312 n.methodHandler.post = h 313 case PROPFIND: 314 n.methodHandler.propfind = h 315 case http.MethodPut: 316 n.methodHandler.put = h 317 case http.MethodTrace: 318 n.methodHandler.trace = h 319 case REPORT: 320 n.methodHandler.report = h 321 } 322 323 if h != nil { 324 n.isHandler = true 325 } else { 326 n.isHandler = n.methodHandler.isHandler() 327 } 328} 329 330func (n *node) findHandler(method string) HandlerFunc { 331 switch method { 332 case http.MethodConnect: 333 return n.methodHandler.connect 334 case http.MethodDelete: 335 return n.methodHandler.delete 336 case http.MethodGet: 337 return n.methodHandler.get 338 case http.MethodHead: 339 return n.methodHandler.head 340 case http.MethodOptions: 341 return n.methodHandler.options 342 case http.MethodPatch: 343 return n.methodHandler.patch 344 case http.MethodPost: 345 return n.methodHandler.post 346 case PROPFIND: 347 return n.methodHandler.propfind 348 case http.MethodPut: 349 return n.methodHandler.put 350 case http.MethodTrace: 351 return n.methodHandler.trace 352 case REPORT: 353 return n.methodHandler.report 354 default: 355 return nil 356 } 357} 358 359func (n *node) checkMethodNotAllowed() HandlerFunc { 360 for _, m := range methods { 361 if h := n.findHandler(m); h != nil { 362 return MethodNotAllowedHandler 363 } 364 } 365 return NotFoundHandler 366} 367 368// Find lookup a handler registered for method and path. It also parses URL for path 369// parameters and load them into context. 370// 371// For performance: 372// 373// - Get context from `Echo#AcquireContext()` 374// - Reset it `Context#Reset()` 375// - Return it `Echo#ReleaseContext()`. 376func (r *Router) Find(method, path string, c Context) { 377 ctx := c.(*context) 378 ctx.path = path 379 currentNode := r.tree // Current node as root 380 381 var ( 382 previousBestMatchNode *node 383 matchedHandler HandlerFunc 384 // search stores the remaining path to check for match. By each iteration we move from start of path to end of the path 385 // and search value gets shorter and shorter. 386 search = path 387 searchIndex = 0 388 paramIndex int // Param counter 389 paramValues = ctx.pvalues // Use the internal slice so the interface can keep the illusion of a dynamic slice 390 ) 391 392 // Backtracking is needed when a dead end (leaf node) is reached in the router tree. 393 // To backtrack the current node will be changed to the parent node and the next kind for the 394 // router logic will be returned based on fromKind or kind of the dead end node (static > param > any). 395 // For example if there is no static node match we should check parent next sibling by kind (param). 396 // Backtracking itself does not check if there is a next sibling, this is done by the router logic. 397 backtrackToNextNodeKind := func(fromKind kind) (nextNodeKind kind, valid bool) { 398 previous := currentNode 399 currentNode = previous.parent 400 valid = currentNode != nil 401 402 // Next node type by priority 403 if previous.kind == anyKind { 404 nextNodeKind = staticKind 405 } else { 406 nextNodeKind = previous.kind + 1 407 } 408 409 if fromKind == staticKind { 410 // when backtracking is done from static kind block we did not change search so nothing to restore 411 return 412 } 413 414 // restore search to value it was before we move to current node we are backtracking from. 415 if previous.kind == staticKind { 416 searchIndex -= len(previous.prefix) 417 } else { 418 paramIndex-- 419 // for param/any node.prefix value is always `:` so we can not deduce searchIndex from that and must use pValue 420 // for that index as it would also contain part of path we cut off before moving into node we are backtracking from 421 searchIndex -= len(paramValues[paramIndex]) 422 paramValues[paramIndex] = "" 423 } 424 search = path[searchIndex:] 425 return 426 } 427 428 // Router tree is implemented by longest common prefix array (LCP array) https://en.wikipedia.org/wiki/LCP_array 429 // Tree search is implemented as for loop where one loop iteration is divided into 3 separate blocks 430 // Each of these blocks checks specific kind of node (static/param/any). Order of blocks reflex their priority in routing. 431 // Search order/priority is: static > param > any. 432 // 433 // Note: backtracking in tree is implemented by replacing/switching currentNode to previous node 434 // and hoping to (goto statement) next block by priority to check if it is the match. 435 for { 436 prefixLen := 0 // Prefix length 437 lcpLen := 0 // LCP (longest common prefix) length 438 439 if currentNode.kind == staticKind { 440 searchLen := len(search) 441 prefixLen = len(currentNode.prefix) 442 443 // LCP - Longest Common Prefix (https://en.wikipedia.org/wiki/LCP_array) 444 max := prefixLen 445 if searchLen < max { 446 max = searchLen 447 } 448 for ; lcpLen < max && search[lcpLen] == currentNode.prefix[lcpLen]; lcpLen++ { 449 } 450 } 451 452 if lcpLen != prefixLen { 453 // No matching prefix, let's backtrack to the first possible alternative node of the decision path 454 nk, ok := backtrackToNextNodeKind(staticKind) 455 if !ok { 456 return // No other possibilities on the decision path 457 } else if nk == paramKind { 458 goto Param 459 // NOTE: this case (backtracking from static node to previous any node) can not happen by current any matching logic. Any node is end of search currently 460 //} else if nk == anyKind { 461 // goto Any 462 } else { 463 // Not found (this should never be possible for static node we are looking currently) 464 break 465 } 466 } 467 468 // The full prefix has matched, remove the prefix from the remaining search 469 search = search[lcpLen:] 470 searchIndex = searchIndex + lcpLen 471 472 // Finish routing if no remaining search and we are on a node with handler and matching method type 473 if search == "" && currentNode.isHandler { 474 // check if current node has handler registered for http method we are looking for. we store currentNode as 475 // best matching in case we do no find no more routes matching this path+method 476 if previousBestMatchNode == nil { 477 previousBestMatchNode = currentNode 478 } 479 if h := currentNode.findHandler(method); h != nil { 480 matchedHandler = h 481 break 482 } 483 } 484 485 // Static node 486 if search != "" { 487 if child := currentNode.findStaticChild(search[0]); child != nil { 488 currentNode = child 489 continue 490 } 491 } 492 493 Param: 494 // Param node 495 if child := currentNode.paramChild; search != "" && child != nil { 496 currentNode = child 497 i := 0 498 l := len(search) 499 if currentNode.isLeaf { 500 // when param node does not have any children then param node should act similarly to any node - consider all remaining search as match 501 i = l 502 } else { 503 for ; i < l && search[i] != '/'; i++ { 504 } 505 } 506 507 paramValues[paramIndex] = search[:i] 508 paramIndex++ 509 search = search[i:] 510 searchIndex = searchIndex + i 511 continue 512 } 513 514 Any: 515 // Any node 516 if child := currentNode.anyChild; child != nil { 517 // If any node is found, use remaining path for paramValues 518 currentNode = child 519 paramValues[len(currentNode.pnames)-1] = search 520 // update indexes/search in case we need to backtrack when no handler match is found 521 paramIndex++ 522 searchIndex += +len(search) 523 search = "" 524 525 // check if current node has handler registered for http method we are looking for. we store currentNode as 526 // best matching in case we do no find no more routes matching this path+method 527 if previousBestMatchNode == nil { 528 previousBestMatchNode = currentNode 529 } 530 if h := currentNode.findHandler(method); h != nil { 531 matchedHandler = h 532 break 533 } 534 } 535 536 // Let's backtrack to the first possible alternative node of the decision path 537 nk, ok := backtrackToNextNodeKind(anyKind) 538 if !ok { 539 break // No other possibilities on the decision path 540 } else if nk == paramKind { 541 goto Param 542 } else if nk == anyKind { 543 goto Any 544 } else { 545 // Not found 546 break 547 } 548 } 549 550 if currentNode == nil && previousBestMatchNode == nil { 551 return // nothing matched at all 552 } 553 554 if matchedHandler != nil { 555 ctx.handler = matchedHandler 556 } else { 557 // use previous match as basis. although we have no matching handler we have path match. 558 // so we can send http.StatusMethodNotAllowed (405) instead of http.StatusNotFound (404) 559 currentNode = previousBestMatchNode 560 ctx.handler = currentNode.checkMethodNotAllowed() 561 } 562 ctx.path = currentNode.ppath 563 ctx.pnames = currentNode.pnames 564 565 return 566} 567