diff options
Diffstat (limited to 'vendor/github.com/labstack/echo/router.go')
| -rw-r--r-- | vendor/github.com/labstack/echo/router.go | 436 |
1 files changed, 436 insertions, 0 deletions
diff --git a/vendor/github.com/labstack/echo/router.go b/vendor/github.com/labstack/echo/router.go new file mode 100644 index 00000000..5cb47116 --- /dev/null +++ b/vendor/github.com/labstack/echo/router.go @@ -0,0 +1,436 @@ +package echo + +import "strings" + +type ( + // Router is the registry of all registered routes for an `Echo` instance for + // request matching and URL path parameter parsing. + Router struct { + tree *node + routes map[string]Route + echo *Echo + } + node struct { + kind kind + label byte + prefix string + parent *node + children children + ppath string + pnames []string + methodHandler *methodHandler + } + kind uint8 + children []*node + methodHandler struct { + connect HandlerFunc + delete HandlerFunc + get HandlerFunc + head HandlerFunc + options HandlerFunc + patch HandlerFunc + post HandlerFunc + put HandlerFunc + trace HandlerFunc + } +) + +const ( + skind kind = iota + pkind + akind +) + +// NewRouter returns a new Router instance. +func NewRouter(e *Echo) *Router { + return &Router{ + tree: &node{ + methodHandler: new(methodHandler), + }, + routes: make(map[string]Route), + echo: e, + } +} + +// Add registers a new route for method and path with matching handler. +func (r *Router) Add(method, path string, h HandlerFunc) { + // Validate path + if path == "" { + panic("echo: path cannot be empty") + } + if path[0] != '/' { + path = "/" + path + } + ppath := path // Pristine path + pnames := []string{} // Param names + + for i, l := 0, len(path); i < l; i++ { + if path[i] == ':' { + j := i + 1 + + r.insert(method, path[:i], nil, skind, "", nil) + for ; i < l && path[i] != '/'; i++ { + } + + pnames = append(pnames, path[j:i]) + path = path[:j] + path[i:] + i, l = j, len(path) + + if i == l { + r.insert(method, path[:i], h, pkind, ppath, pnames) + return + } + r.insert(method, path[:i], nil, pkind, ppath, pnames) + } else if path[i] == '*' { + r.insert(method, path[:i], nil, skind, "", nil) + pnames = append(pnames, "*") + r.insert(method, path[:i+1], h, akind, ppath, pnames) + return + } + } + + r.insert(method, path, h, skind, ppath, pnames) +} + +func (r *Router) insert(method, path string, h HandlerFunc, t kind, ppath string, pnames []string) { + // Adjust max param + l := len(pnames) + if *r.echo.maxParam < l { + *r.echo.maxParam = l + } + + cn := r.tree // Current node as root + if cn == nil { + panic("echo ⇛ invalid method") + } + search := path + + for { + sl := len(search) + pl := len(cn.prefix) + l := 0 + + // LCP + max := pl + if sl < max { + max = sl + } + for ; l < max && search[l] == cn.prefix[l]; l++ { + } + + if l == 0 { + // At root node + cn.label = search[0] + cn.prefix = search + if h != nil { + cn.kind = t + cn.addHandler(method, h) + cn.ppath = ppath + cn.pnames = pnames + } + } else if l < pl { + // Split node + n := newNode(cn.kind, cn.prefix[l:], cn, cn.children, cn.methodHandler, cn.ppath, cn.pnames) + + // Reset parent node + cn.kind = skind + cn.label = cn.prefix[0] + cn.prefix = cn.prefix[:l] + cn.children = nil + cn.methodHandler = new(methodHandler) + cn.ppath = "" + cn.pnames = nil + + cn.addChild(n) + + if l == sl { + // At parent node + cn.kind = t + cn.addHandler(method, h) + cn.ppath = ppath + cn.pnames = pnames + } else { + // Create child node + n = newNode(t, search[l:], cn, nil, new(methodHandler), ppath, pnames) + n.addHandler(method, h) + cn.addChild(n) + } + } else if l < sl { + search = search[l:] + c := cn.findChildWithLabel(search[0]) + if c != nil { + // Go deeper + cn = c + continue + } + // Create child node + n := newNode(t, search, cn, nil, new(methodHandler), ppath, pnames) + n.addHandler(method, h) + cn.addChild(n) + } else { + // Node already exists + if h != nil { + cn.addHandler(method, h) + cn.ppath = ppath + if len(cn.pnames) == 0 { // Issue #729 + cn.pnames = pnames + } + for i, n := range pnames { + // Param name aliases + if i < len(cn.pnames) && !strings.Contains(cn.pnames[i], n) { + cn.pnames[i] += "," + n + } + } + } + } + return + } +} + +func newNode(t kind, pre string, p *node, c children, mh *methodHandler, ppath string, pnames []string) *node { + return &node{ + kind: t, + label: pre[0], + prefix: pre, + parent: p, + children: c, + ppath: ppath, + pnames: pnames, + methodHandler: mh, + } +} + +func (n *node) addChild(c *node) { + n.children = append(n.children, c) +} + +func (n *node) findChild(l byte, t kind) *node { + for _, c := range n.children { + if c.label == l && c.kind == t { + return c + } + } + return nil +} + +func (n *node) findChildWithLabel(l byte) *node { + for _, c := range n.children { + if c.label == l { + return c + } + } + return nil +} + +func (n *node) findChildByKind(t kind) *node { + for _, c := range n.children { + if c.kind == t { + return c + } + } + return nil +} + +func (n *node) addHandler(method string, h HandlerFunc) { + switch method { + case GET: + n.methodHandler.get = h + case POST: + n.methodHandler.post = h + case PUT: + n.methodHandler.put = h + case DELETE: + n.methodHandler.delete = h + case PATCH: + n.methodHandler.patch = h + case OPTIONS: + n.methodHandler.options = h + case HEAD: + n.methodHandler.head = h + case CONNECT: + n.methodHandler.connect = h + case TRACE: + n.methodHandler.trace = h + } +} + +func (n *node) findHandler(method string) HandlerFunc { + switch method { + case GET: + return n.methodHandler.get + case POST: + return n.methodHandler.post + case PUT: + return n.methodHandler.put + case DELETE: + return n.methodHandler.delete + case PATCH: + return n.methodHandler.patch + case OPTIONS: + return n.methodHandler.options + case HEAD: + return n.methodHandler.head + case CONNECT: + return n.methodHandler.connect + case TRACE: + return n.methodHandler.trace + default: + return nil + } +} + +func (n *node) checkMethodNotAllowed() HandlerFunc { + for _, m := range methods { + if h := n.findHandler(m); h != nil { + return MethodNotAllowedHandler + } + } + return NotFoundHandler +} + +// Find lookup a handler registered for method and path. It also parses URL for path +// parameters and load them into context. +// +// For performance: +// +// - Get context from `Echo#AcquireContext()` +// - Reset it `Context#Reset()` +// - Return it `Echo#ReleaseContext()`. +func (r *Router) Find(method, path string, context Context) { + context.SetPath(path) + cn := r.tree // Current node as root + + var ( + search = path + c *node // Child node + n int // Param counter + nk kind // Next kind + nn *node // Next node + ns string // Next search + pvalues = context.ParamValues() + ) + + // Search order static > param > any + for { + if search == "" { + goto End + } + + pl := 0 // Prefix length + l := 0 // LCP length + + if cn.label != ':' { + sl := len(search) + pl = len(cn.prefix) + + // LCP + max := pl + if sl < max { + max = sl + } + for ; l < max && search[l] == cn.prefix[l]; l++ { + } + } + + if l == pl { + // Continue search + search = search[l:] + } else { + cn = nn + search = ns + if nk == pkind { + goto Param + } else if nk == akind { + goto Any + } + // Not found + return + } + + if search == "" { + goto End + } + + // Static node + if c = cn.findChild(search[0], skind); c != nil { + // Save next + if cn.prefix[len(cn.prefix)-1] == '/' { // Issue #623 + nk = pkind + nn = cn + ns = search + } + cn = c + continue + } + + // Param node + Param: + if c = cn.findChildByKind(pkind); c != nil { + // Issue #378 + if len(pvalues) == n { + continue + } + + // Save next + if cn.prefix[len(cn.prefix)-1] == '/' { // Issue #623 + nk = akind + nn = cn + ns = search + } + + cn = c + i, l := 0, len(search) + for ; i < l && search[i] != '/'; i++ { + } + pvalues[n] = search[:i] + n++ + search = search[i:] + continue + } + + // Any node + Any: + if cn = cn.findChildByKind(akind); cn == nil { + if nn != nil { + cn = nn + nn = nil // Next + search = ns + if nk == pkind { + goto Param + } else if nk == akind { + goto Any + } + } + // Not found + return + } + pvalues[len(cn.pnames)-1] = search + goto End + } + +End: + context.SetHandler(cn.findHandler(method)) + context.SetPath(cn.ppath) + context.SetParamNames(cn.pnames...) + + // NOTE: Slow zone... + if context.Handler() == nil { + context.SetHandler(cn.checkMethodNotAllowed()) + + // Dig further for any, might have an empty value for *, e.g. + // serving a directory. Issue #207. + if cn = cn.findChildByKind(akind); cn == nil { + return + } + if h := cn.findHandler(method); h != nil { + context.SetHandler(h) + } else { + context.SetHandler(cn.checkMethodNotAllowed()) + } + context.SetPath(cn.ppath) + context.SetParamNames(cn.pnames...) + pvalues[len(cn.pnames)-1] = "" + } + + return +} |