1// +build !goji_router_simple
2
3package goji
4
5import (
6	"net/http"
7	"sort"
8	"strings"
9
10	"goji.io/internal"
11)
12
13type router struct {
14	routes   []route
15	methods  map[string]*trieNode
16	wildcard trieNode
17}
18
19type route struct {
20	Pattern
21	http.Handler
22}
23
24type child struct {
25	prefix string
26	node   *trieNode
27}
28
29type trieNode struct {
30	routes   []int
31	children []child
32}
33
34func (rt *router) add(p Pattern, h http.Handler) {
35	i := len(rt.routes)
36	rt.routes = append(rt.routes, route{p, h})
37
38	var prefix string
39	if pp, ok := p.(pathPrefix); ok {
40		prefix = pp.PathPrefix()
41	}
42
43	var methods map[string]struct{}
44	if hm, ok := p.(httpMethods); ok {
45		methods = hm.HTTPMethods()
46	}
47	if methods == nil {
48		rt.wildcard.add(prefix, i)
49		for _, sub := range rt.methods {
50			sub.add(prefix, i)
51		}
52	} else {
53		if rt.methods == nil {
54			rt.methods = make(map[string]*trieNode)
55		}
56
57		for method := range methods {
58			if _, ok := rt.methods[method]; !ok {
59				rt.methods[method] = rt.wildcard.clone()
60			}
61			rt.methods[method].add(prefix, i)
62		}
63	}
64}
65
66func (rt *router) route(r *http.Request) *http.Request {
67	tn := &rt.wildcard
68	if tn2, ok := rt.methods[r.Method]; ok {
69		tn = tn2
70	}
71
72	ctx := r.Context()
73	path := ctx.Value(internal.Path).(string)
74	for path != "" {
75		i := sort.Search(len(tn.children), func(i int) bool {
76			return path[0] <= tn.children[i].prefix[0]
77		})
78		if i == len(tn.children) || !strings.HasPrefix(path, tn.children[i].prefix) {
79			break
80		}
81
82		path = path[len(tn.children[i].prefix):]
83		tn = tn.children[i].node
84	}
85	for _, i := range tn.routes {
86		if r2 := rt.routes[i].Match(r); r2 != nil {
87			return r2.WithContext(&match{
88				Context: r2.Context(),
89				p:       rt.routes[i].Pattern,
90				h:       rt.routes[i].Handler,
91			})
92		}
93	}
94	return r.WithContext(&match{Context: ctx})
95}
96
97// We can be a teensy bit more efficient here: we're maintaining a sorted list,
98// so we know exactly where to insert the new element. But since that involves
99// more bookkeeping and makes the code messier, let's cross that bridge when we
100// come to it.
101type byPrefix []child
102
103func (b byPrefix) Len() int {
104	return len(b)
105}
106func (b byPrefix) Less(i, j int) bool {
107	return b[i].prefix < b[j].prefix
108}
109func (b byPrefix) Swap(i, j int) {
110	b[i], b[j] = b[j], b[i]
111}
112
113func longestPrefix(a, b string) string {
114	mlen := len(a)
115	if len(b) < mlen {
116		mlen = len(b)
117	}
118	for i := 0; i < mlen; i++ {
119		if a[i] != b[i] {
120			return a[:i]
121		}
122	}
123	return a[:mlen]
124}
125
126func (tn *trieNode) add(prefix string, idx int) {
127	if len(prefix) == 0 {
128		tn.routes = append(tn.routes, idx)
129		for i := range tn.children {
130			tn.children[i].node.add(prefix, idx)
131		}
132		return
133	}
134
135	ch := prefix[0]
136	i := sort.Search(len(tn.children), func(i int) bool {
137		return ch <= tn.children[i].prefix[0]
138	})
139
140	if i == len(tn.children) || ch != tn.children[i].prefix[0] {
141		routes := append([]int(nil), tn.routes...)
142		tn.children = append(tn.children, child{
143			prefix: prefix,
144			node:   &trieNode{routes: append(routes, idx)},
145		})
146	} else {
147		lp := longestPrefix(prefix, tn.children[i].prefix)
148
149		if tn.children[i].prefix == lp {
150			tn.children[i].node.add(prefix[len(lp):], idx)
151			return
152		}
153
154		split := new(trieNode)
155		split.children = []child{
156			{tn.children[i].prefix[len(lp):], tn.children[i].node},
157		}
158		split.routes = append([]int(nil), tn.routes...)
159		split.add(prefix[len(lp):], idx)
160
161		tn.children[i].prefix = lp
162		tn.children[i].node = split
163	}
164
165	sort.Sort(byPrefix(tn.children))
166}
167
168func (tn *trieNode) clone() *trieNode {
169	clone := new(trieNode)
170	clone.routes = append(clone.routes, tn.routes...)
171	clone.children = append(clone.children, tn.children...)
172	for i := range clone.children {
173		clone.children[i].node = tn.children[i].node.clone()
174	}
175	return clone
176}
177