trout

     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/doc.go	Mon Mar 16 00:10:38 2015 -0400
     1.3 @@ -0,0 +1,66 @@
     1.4 +/*
     1.5 +Package trout provides an opinionated router that's implemented
     1.6 +using a basic trie.
     1.7 +
     1.8 +The router is opinionated and biased towards basic RESTful
     1.9 +services. Its main constraint is that its URL templating is very
    1.10 +basic and has no support for regular expressions, prefix matching,
    1.11 +or anything other than a direct equality comparison, unlike many
    1.12 +routing libraries.
    1.13 +
    1.14 +The router is specifically designed to support users that want to
    1.15 +return correct information with HEAD requests, so it enables users
    1.16 +to retrieve a list of HTTP methods an Endpoint is configured to
    1.17 +respond to. It will not return the configurations an Endpoint is
    1.18 +implicitly configured to respond to by associated a Handler with the
    1.19 +Endpoint itself. These HTTP methods can be accessed through the
    1.20 +Trout-Methods header that is injected into the http.Request object.
    1.21 +Each method will be its own string in the slice.
    1.22 +
    1.23 +The router is also specifically designed to differentiate between a
    1.24 +404 (Not Found) response and a 405 (Method Not Allowed) response. It
    1.25 +will use the configured Handle404 http.Handler when no Endpoint is found
    1.26 +that matches the http.Request's Path property. It will use the
    1.27 +configured Handle405 http.Handler when an Endpoint is found for the
    1.28 +http.Request's Path, but the http.Request's Method has no Handler
    1.29 +associated with it. Setting a default http.Handler for the Endpoint will
    1.30 +result in the Handle405 http.Handler never being used for that Endpoint.
    1.31 +
    1.32 +To map an Endpoint to a http.Handler:
    1.33 +
    1.34 +	var router trout.Router
    1.35 +	router.Endpoint("/posts/{slug}/comments/{id}").Handler(postsHandler)
    1.36 +
    1.37 +All requests that match that URL structure will be passed to the postsHandler,
    1.38 +no matter what HTTP method they use.
    1.39 +
    1.40 +To map specific Methods to a http.Handler:
    1.41 +
    1.42 +	var router trout.Router
    1.43 +	router.Endpoint("/posts/{slug}").Methods("GET", "POST").Handler(postsHandler)
    1.44 +
    1.45 +Only requests that match that URL structure will be passed to the postsHandler,
    1.46 +and only if they use the GET or POST HTTP method.
    1.47 +
    1.48 +To access the URL parameter values inside a request, use the RequestVars helper:
    1.49 +
    1.50 +	func handler(w http.ResponseWriter, r *http.Request) {
    1.51 +		vars := trout.RequestVars(r)
    1.52 +		...
    1.53 +	}
    1.54 +
    1.55 +This will return an http.Header object containing the parameter values. They are
    1.56 +passed into the http.Handler by injecting them into the http.Request's Header property,
    1.57 +with the header key of "Trout-Params-{parameter}". The RequestVars helper is just a
    1.58 +convenience function to strip the prefix. Parameters are always passed without the curly
    1.59 +braces. Finally, if a parameter name is used multiple times in a single URL template, values
    1.60 +will be stored in the slice in the order they appeared in the template:
    1.61 +
    1.62 +	// for the template /posts/{id}/comments/{id}
    1.63 +	// filled with /posts/hello-world/comments/1
    1.64 +	vars := trout.RequestVars(r)
    1.65 +	fmt.Println(vars.Get("id")) // outputs `hello-world`
    1.66 +	fmt.Println(vars[http.CanonicalHeaderKey("id")]) // outputs `["hello-world", "1"]`
    1.67 +	fmt.Println(vars[http.CanonicalHeaderKey("id"})][1]) // outputs `1`
    1.68 +*/
    1.69 +package trout

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/route.go	Mon Mar 16 00:10:38 2015 -0400
     2.3 @@ -0,0 +1,259 @@
     2.4 +package trout
     2.5 +
     2.6 +import (
     2.7 +	"net/http"
     2.8 +	"strconv"
     2.9 +	"strings"
    2.10 +	"time"
    2.11 +)
    2.12 +
    2.13 +var (
    2.14 +	default404Handler = http.Handler(http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
    2.15 +		w.WriteHeader(http.StatusNotFound)
    2.16 +		w.Write([]byte("404 Not Found"))
    2.17 +		return
    2.18 +	}))
    2.19 +	default405Handler = http.Handler(http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
    2.20 +		w.WriteHeader(http.StatusMethodNotAllowed)
    2.21 +		w.Write([]byte("405 Method Not Allowed"))
    2.22 +		return
    2.23 +	}))
    2.24 +)
    2.25 +
    2.26 +// RequestVars returns easy-to-access mappings of parameters to values for URL templates. Any {parameter} in
    2.27 +// your URL template will be available in the returned Header as a slice of strings, one for each instance of
    2.28 +// the {parameter}. In the case of a parameter name being used more than once in the same URL template, the
    2.29 +// values will be in the slice in the order they appeared in the template.
    2.30 +//
    2.31 +// Values can easily be accessed by using the .Get() method of the returned Header, though to access multiple
    2.32 +// values, they must be accessed through the map. All parameters use http.CanonicalHeaderKey for their formatting.
    2.33 +// When using .Get(), the parameter name will be transformed automatically. When utilising the Header as a map,
    2.34 +// the parameter name needs to have http.CanonicalHeaderKey applied manually.
    2.35 +func RequestVars(r *http.Request) http.Header {
    2.36 +	res := http.Header{}
    2.37 +	for h, v := range r.Header {
    2.38 +		stripped := strings.TrimPrefix(h, http.CanonicalHeaderKey("Trout-Param-"))
    2.39 +		if stripped != h {
    2.40 +			res[stripped] = v
    2.41 +		}
    2.42 +	}
    2.43 +	return res
    2.44 +}
    2.45 +
    2.46 +// Router defines a set of Endpoints that map requests to the http.Handlers. The http.Handler assigned to
    2.47 +// Handle404, if set, will be called when no Endpoint matches the current request. The http.Handler assigned
    2.48 +// to Handle405, if set, will be called when an Endpoint matches the current request, but has no http.Handler
    2.49 +// set for the HTTP method that the request used. Should either of these properties be unset, a default
    2.50 +// http.Handler will be used.
    2.51 +//
    2.52 +// The Router type is safe for use with empty values, but makes no attempt at concurrency-safety in adding
    2.53 +// Endpoints or in setting properties. It should also be noted that the adding Endpoints while simultaneously
    2.54 +// routing requests will lead to undefined and (almost certainly) undesirable behaviour. Routers are intended
    2.55 +// to be initialised with a set of Endpoints, and then start serving requests. Using them outside of this use
    2.56 +// case is unsupported.
    2.57 +type Router struct {
    2.58 +	t         *trie
    2.59 +	Handle404 http.Handler
    2.60 +	Handle405 http.Handler
    2.61 +}
    2.62 +
    2.63 +func (router Router) serve404(w http.ResponseWriter, r *http.Request, t time.Time) {
    2.64 +	h := default404Handler
    2.65 +	if router.Handle404 != nil {
    2.66 +		h = router.Handle404
    2.67 +	}
    2.68 +	r.Header.Set("Trout-Timer", strconv.FormatInt(time.Now().Sub(t).Nanoseconds(), 10))
    2.69 +	h.ServeHTTP(w, r)
    2.70 +}
    2.71 +
    2.72 +func (router Router) serve405(w http.ResponseWriter, r *http.Request, t time.Time) {
    2.73 +	h := default405Handler
    2.74 +	if router.Handle405 != nil {
    2.75 +		h = router.Handle405
    2.76 +	}
    2.77 +	r.Header.Set("Trout-Timer", strconv.FormatInt(time.Now().Sub(t).Nanoseconds(), 10))
    2.78 +	h.ServeHTTP(w, r)
    2.79 +}
    2.80 +
    2.81 +func (router Router) ServeHTTP(w http.ResponseWriter, r *http.Request) {
    2.82 +	start := time.Now()
    2.83 +	if router.t == nil {
    2.84 +		router.serve404(w, r, start)
    2.85 +	}
    2.86 +	pieces := strings.Split(strings.ToLower(strings.Trim(r.URL.Path, "/")), "/")
    2.87 +	router.t.RLock()
    2.88 +	defer router.t.RUnlock()
    2.89 +	branches := make([]*branch, len(pieces))
    2.90 +	path, ok := router.t.match(pieces)
    2.91 +	if !ok {
    2.92 +		router.serve404(w, r, start)
    2.93 +	}
    2.94 +	b := router.t.branch
    2.95 +	for i, pos := range path {
    2.96 +		b = b.children[pos]
    2.97 +		branches[i] = b
    2.98 +	}
    2.99 +	v := vars(branches, pieces)
   2.100 +	for key, vals := range v {
   2.101 +		r.Header[http.CanonicalHeaderKey("Trout-Param-"+key)] = vals
   2.102 +	}
   2.103 +	ms := make([]string, len(b.methods))
   2.104 +	i := 0
   2.105 +	for m := range b.methods {
   2.106 +		ms[i] = m
   2.107 +		i = i + 1
   2.108 +	}
   2.109 +	r.Header[http.CanonicalHeaderKey("Trout-Methods")] = ms
   2.110 +	h := b.methods[r.Method]
   2.111 +	if h == nil {
   2.112 +		router.serve405(w, r, start)
   2.113 +	}
   2.114 +	r.Header.Set("Trout-Timer", strconv.FormatInt(time.Now().Sub(start).Nanoseconds(), 10))
   2.115 +	h.ServeHTTP(w, r)
   2.116 +}
   2.117 +
   2.118 +// Endpoint defines a new Endpoint on the Router. The Endpoint should be a URL template, using curly braces
   2.119 +// to denote parameters that should be filled at runtime. For example, `{id}` denotes a parameter named `id`
   2.120 +// that should be filled with whatever the request has in that space.
   2.121 +//
   2.122 +// Parameters are always `/`-separated strings. There is no support for regular expressions or other limitations
   2.123 +// on what may be in those strings. A parameter is simply defined as "whatever is between these two / characters".
   2.124 +func (router Router) Endpoint(e string) *Endpoint {
   2.125 +	e = strings.Trim(e, "/")
   2.126 +	e = strings.ToLower(e)
   2.127 +	pieces := strings.Split(e, "/")
   2.128 +	router.t.Lock()
   2.129 +	defer router.t.Unlock()
   2.130 +	if router.t.branch == nil {
   2.131 +		router.t.branch = &branch{
   2.132 +			parent:   nil,
   2.133 +			children: []*branch{},
   2.134 +			key:      "",
   2.135 +			isParam:  false,
   2.136 +			methods:  map[string]http.Handler{},
   2.137 +		}
   2.138 +	}
   2.139 +	closest := findClosestLeaf(pieces, router.t.branch)
   2.140 +	b := router.t.branch
   2.141 +	for _, pos := range closest {
   2.142 +		b = b.children[pos]
   2.143 +	}
   2.144 +	if len(closest) == len(pieces) {
   2.145 +		return (*Endpoint)(b)
   2.146 +	}
   2.147 +	offset := len(closest)
   2.148 +	for i := offset; i < len(pieces); i++ {
   2.149 +		piece := pieces[i]
   2.150 +		var isParam bool
   2.151 +		if piece[0:1] == "{" && piece[len(piece)-1:] == "}" {
   2.152 +			isParam = true
   2.153 +			piece = piece[1 : len(piece)-1]
   2.154 +		}
   2.155 +		b = b.addChild(piece, isParam)
   2.156 +	}
   2.157 +	return (*Endpoint)(b)
   2.158 +}
   2.159 +
   2.160 +func vars(path []*branch, pieces []string) map[string][]string {
   2.161 +	v := map[string][]string{}
   2.162 +	for pos, p := range path {
   2.163 +		if !p.isParam {
   2.164 +			continue
   2.165 +		}
   2.166 +		_, ok := v[p.key]
   2.167 +		if !ok {
   2.168 +			v[p.key] = []string{pieces[pos]}
   2.169 +			continue
   2.170 +		}
   2.171 +		v[p.key] = append(v[p.key], pieces[pos])
   2.172 +	}
   2.173 +	return v
   2.174 +}
   2.175 +
   2.176 +func findClosestLeaf(pieces []string, b *branch) []int {
   2.177 +	offset := 0
   2.178 +	path := []int{}
   2.179 +	longest := []int{}
   2.180 +	num := len(pieces)
   2.181 +	for i := 0; i < num; i++ {
   2.182 +		piece := pieces[i]
   2.183 +		var isParam bool
   2.184 +		if piece[0:1] == "{" && piece[len(piece)-1:] == "}" {
   2.185 +			isParam = true
   2.186 +			piece = piece[1 : len(piece)-1]
   2.187 +		}
   2.188 +		offset = pickNextRoute(b, offset, piece, isParam)
   2.189 +		if offset == -1 {
   2.190 +			if len(path) == 0 {
   2.191 +				// exhausted our options, bail
   2.192 +				break
   2.193 +			}
   2.194 +			// no match, maybe save this and backup
   2.195 +			if len(path) > len(longest) {
   2.196 +				longest = append([]int{}, path...) // copy them over so they don't get modified
   2.197 +			}
   2.198 +			path, offset = backup(path)
   2.199 +			offset = offset + 1
   2.200 +			b = b.parent
   2.201 +			i = i - 2
   2.202 +		} else {
   2.203 +			path = append(path, offset)
   2.204 +			b = b.children[offset]
   2.205 +			offset = 0
   2.206 +		}
   2.207 +	}
   2.208 +	if len(longest) < len(path) {
   2.209 +		longest = append([]int{}, path...)
   2.210 +	}
   2.211 +	return longest
   2.212 +}
   2.213 +
   2.214 +func pickNextRoute(b *branch, offset int, input string, variable bool) int {
   2.215 +	count := len(b.children)
   2.216 +	for i := offset; i < count; i++ {
   2.217 +		if b.children[i].key == input && b.isParam == variable {
   2.218 +			return i
   2.219 +		}
   2.220 +	}
   2.221 +	return -1
   2.222 +}
   2.223 +
   2.224 +// Endpoint defines a single URL template that requests can be matched against. It uses
   2.225 +// URL parameters to accept variables in the URL structure and make them available to
   2.226 +// the Handlers associated with the Endpoint.
   2.227 +type Endpoint branch
   2.228 +
   2.229 +// Handler associates the passed http.Handler with the Endpoint. This http.Handler will be
   2.230 +// used for all requests, regardless of the HTTP method they are using, unless overridden by
   2.231 +// the Methods method. Endpoints without a http.Handler associated with them will not be
   2.232 +// considered matches for requests, unless the request was made using an HTTP method that the
   2.233 +// Endpoint has an http.Handler mapped to.
   2.234 +func (e *Endpoint) Handler(h http.Handler) {
   2.235 +	(*branch)(e).setHandler("", h)
   2.236 +}
   2.237 +
   2.238 +// Methods simple returns a Methods object that will enable the mapping of the passed HTTP
   2.239 +// request methods to a Methods object. On its own, this function does not modify anything. It
   2.240 +// should, instead, be used as a friendly shorthand to get to the Methods.Handler method.
   2.241 +func (e *Endpoint) Methods(m ...string) Methods {
   2.242 +	return Methods{
   2.243 +		e: e,
   2.244 +		m: m,
   2.245 +	}
   2.246 +}
   2.247 +
   2.248 +// Methods defines a pairing of an Endpoint to the HTTP request methods that should be mapped to
   2.249 +// specific http.Handlers. Its sole purpose is to enable the Methods.Handler method.
   2.250 +type Methods struct {
   2.251 +	e *Endpoint
   2.252 +	m []string
   2.253 +}
   2.254 +
   2.255 +// Handler maps a Methods object to a specific http.Handler. This overrides the http.Handler
   2.256 +// associated with the Endpoint to only handle specific HTTP method(s).
   2.257 +func (m Methods) Handler(h http.Handler) {
   2.258 +	b := (*branch)(m.e)
   2.259 +	for _, method := range m.m {
   2.260 +		b.setHandler(method, h)
   2.261 +	}
   2.262 +}

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/trie.go	Mon Mar 16 00:10:38 2015 -0400
     3.3 @@ -0,0 +1,110 @@
     3.4 +package trout
     3.5 +
     3.6 +import (
     3.7 +	"net/http"
     3.8 +	"sort"
     3.9 +	"sync"
    3.10 +)
    3.11 +
    3.12 +type trie struct {
    3.13 +	branch *branch
    3.14 +	sync.RWMutex
    3.15 +}
    3.16 +
    3.17 +func (t *trie) match(input []string) ([]int, bool) {
    3.18 +	if t.branch == nil {
    3.19 +		t.branch = &branch{}
    3.20 +	}
    3.21 +	b := t.branch
    3.22 +	path := []int{}
    3.23 +	offset := 0
    3.24 +	num := len(input)
    3.25 +	for i := 0; i < num; i++ {
    3.26 +		// if we're on a nil branch, we're at the end of our line
    3.27 +		if b == nil {
    3.28 +			return path, false
    3.29 +		}
    3.30 +		offset = pickNextBranch(b, offset, input[i])
    3.31 +		if offset == -1 {
    3.32 +			if len(path) == 0 {
    3.33 +				// can't find it, bail
    3.34 +				return path, false
    3.35 +			}
    3.36 +			// no match, backup
    3.37 +			path, offset = backup(path)
    3.38 +			offset = offset + 1 // we want the next index from the previously matched one
    3.39 +			b = b.parent        // we need to be picking a branch from our parent, again
    3.40 +			i = i - 2           // back up to the choice before the one that got us here
    3.41 +		} else {
    3.42 +			path = append(path, offset)
    3.43 +			b = b.children[offset]
    3.44 +			offset = 0
    3.45 +		}
    3.46 +	}
    3.47 +	return path, true
    3.48 +}
    3.49 +
    3.50 +type branch struct {
    3.51 +	parent   *branch
    3.52 +	children []*branch
    3.53 +	key      string
    3.54 +	isParam  bool
    3.55 +	methods  map[string]http.Handler
    3.56 +}
    3.57 +
    3.58 +func (b *branch) Less(i, j int) bool {
    3.59 +	if b.children[i].key == b.children[j].key {
    3.60 +		return b.children[j].isParam && !b.children[i].isParam
    3.61 +	}
    3.62 +	return b.children[i].key < b.children[j].key
    3.63 +}
    3.64 +
    3.65 +func (b *branch) Len() int {
    3.66 +	return len(b.children)
    3.67 +}
    3.68 +
    3.69 +func (b *branch) Swap(i, j int) {
    3.70 +	b.children[i], b.children[j] = b.children[j], b.children[i]
    3.71 +}
    3.72 +
    3.73 +func (b *branch) addChild(key string, param bool) *branch {
    3.74 +	child := &branch{key: key, parent: b, isParam: param}
    3.75 +	if b.children == nil {
    3.76 +		b.children = []*branch{child}
    3.77 +		return child
    3.78 +	}
    3.79 +	b.children = append(b.children, child)
    3.80 +	sort.Sort(b)
    3.81 +	return child
    3.82 +}
    3.83 +
    3.84 +func (b *branch) check(input string) bool {
    3.85 +	if b.isParam && b.key != "" {
    3.86 +		return true
    3.87 +	}
    3.88 +	if b.key == input {
    3.89 +		return true
    3.90 +	}
    3.91 +	return false
    3.92 +}
    3.93 +
    3.94 +func (b *branch) setHandler(method string, handler http.Handler) {
    3.95 +	b.methods[method] = handler
    3.96 +}
    3.97 +
    3.98 +func pickNextBranch(b *branch, offset int, input string) int {
    3.99 +	count := len(b.children)
   3.100 +	for i := offset; i < count; i++ {
   3.101 +		if b.children[i].check(input) {
   3.102 +			return i
   3.103 +		}
   3.104 +	}
   3.105 +	return -1
   3.106 +}
   3.107 +
   3.108 +func backup(path []int) ([]int, int) {
   3.109 +	last := len(path) - 1
   3.110 +	pos := path[last]
   3.111 +	path = path[:last]
   3.112 +	return path, pos
   3.113 +}