Update vendor

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
+}