tree: fix case-insensitive unicode lookup

Fixes #113

tree.go

diff --git a/tree.go b/tree.go
index eeadec9..48f25f9 100644
--- a/tree.go
+++ b/tree.go
@@ -7,6 +7,7 @@
 import (
 	"strings"
 	"unicode"
+	"unicode/utf8"
 )
 
 func min(a, b int) int {
@@ -447,34 +448,64 @@
 // It returns the case-corrected path and a bool indicating whether the lookup
 // was successful.
 func (n *node) findCaseInsensitivePath(path string, fixTrailingSlash bool) (ciPath []byte, found bool) {
-	ciPath = make([]byte, 0, len(path)+1) // preallocate enough memory
+	return n.findCaseInsensitivePathRec(
+		path,
+		strings.ToLower(path),
+		make([]byte, 0, len(path)+1), // preallocate enough memory for new path
+		[4]byte{},                    // empty rune buffer
+		fixTrailingSlash,
+	)
+}
+
+func (n *node) findCaseInsensitivePathRec(path, loPath string, ciPath []byte, rb [4]byte, fixTrailingSlash bool) ([]byte, bool) {
+	loNPath := strings.ToLower(n.path)
 
 	// Outer loop for walking the tree
-	for len(path) >= len(n.path) && strings.ToLower(path[:len(n.path)]) == strings.ToLower(n.path) {
-		path = path[len(n.path):]
+	for len(loPath) >= len(loNPath) && loPath[:len(loNPath)] == loNPath {
+		// add common path to result
 		ciPath = append(ciPath, n.path...)
 
+		path = path[len(n.path):]
+		loPath = loPath[len(loNPath):]
+
 		if len(path) > 0 {
 			// If this node does not have a wildcard (param or catchAll) child,
 			// we can just look up the next child node and continue to walk down
 			// the tree
 			if !n.wildChild {
-				r := unicode.ToLower(rune(path[0]))
-				for i, index := range n.indices {
-					// must use recursive approach since both index and
-					// ToLower(index) could exist. We must check both.
-					if r == unicode.ToLower(index) {
-						out, found := n.children[i].findCaseInsensitivePath(path, fixTrailingSlash)
-						if found {
-							return append(ciPath, out...), true
-						}
+				// get lowercase and uppercase runes
+				var lr, ur [4]byte
+				if rb[0] != 0 {
+					// old rune not finished
+					lr = rb
+				} else {
+					// start a new rune
+					rv, _ := utf8.DecodeRuneInString(loPath)
+					utf8.EncodeRune(lr[:], rv)
+					utf8.EncodeRune(ur[:], unicode.ToUpper(rv))
+				}
+
+				for i := 0; i < len(n.indices); i++ {
+					// must use recursive approach since both the uppercase
+					// byte and the lowercase byte might exist as an index.
+					if idx := n.indices[i]; idx == lr[0] {
+						rb = lr // lowercase matches
+					} else if idx == ur[0] {
+						rb = ur // uppercase matches
+					} else {
+						continue // no match, try next index
+					}
+
+					if out, found := n.children[i].findCaseInsensitivePathRec(
+						path, loPath, ciPath,
+						[4]byte{rb[1], rb[2], rb[3], 0}, fixTrailingSlash); found {
+						return out, true
 					}
 				}
 
 				// Nothing found. We can recommend to redirect to the same URL
 				// without a trailing slash if a leaf exists for that path
-				found = (fixTrailingSlash && path == "/" && n.handle != nil)
-				return
+				return ciPath, (fixTrailingSlash && path == "/" && n.handle != nil)
 			}
 
 			n = n.children[0]
@@ -492,8 +523,11 @@
 				// we need to go deeper!
 				if k < len(path) {
 					if len(n.children) > 0 {
+						// continue with child node
 						path = path[k:]
+						loPath = loPath[k:]
 						n = n.children[0]
+						loNPath = strings.ToLower(n.path)
 						continue
 					}
 
@@ -501,7 +535,7 @@
 					if fixTrailingSlash && len(path) == k+1 {
 						return ciPath, true
 					}
-					return
+					return ciPath, false
 				}
 
 				if n.handle != nil {
@@ -514,7 +548,7 @@
 						return append(ciPath, '/'), true
 					}
 				}
-				return
+				return ciPath, false
 
 			case catchAll:
 				return append(ciPath, path...), true
@@ -539,11 +573,11 @@
 							(n.nType == catchAll && n.children[0].handle != nil) {
 							return append(ciPath, '/'), true
 						}
-						return
+						return ciPath, false
 					}
 				}
 			}
-			return
+			return ciPath, false
 		}
 	}
 
@@ -554,10 +588,10 @@
 			return ciPath, true
 		}
 		if len(path)+1 == len(n.path) && n.path[len(path)] == '/' &&
-			strings.ToLower(path) == strings.ToLower(n.path[:len(path)]) &&
+			loPath == loNPath[:len(loPath)] &&
 			n.handle != nil {
 			return append(ciPath, n.path...), true
 		}
 	}
-	return
+	return ciPath, false
 }

tree_test.go

diff --git a/tree_test.go b/tree_test.go
index 531768d..e28e8f1 100644
--- a/tree_test.go
+++ b/tree_test.go
@@ -502,6 +502,10 @@
 		"/doc/go/away",
 		"/no/a",
 		"/no/b",
+		"/Π",
+		"/apfêl/",
+		"/äpfêl/",
+		"/öpfêl",
 	}
 
 	for _, route := range routes {
@@ -580,6 +584,12 @@
 		{"/DOC/", "/doc", true, true},
 		{"/NO", "", false, true},
 		{"/DOC/GO", "", false, true},
+		{"/π", "/Π", true, false},
+		{"/π/", "/Π", true, true},
+		{"/ÄPFÊL/", "/äpfêl/", true, false},
+		{"/ÄPFÊL", "/äpfêl/", true, true},
+		{"/ÖPFÊL/", "/öpfêl", true, true},
+		{"/ÖPFÊL", "/öpfêl", true, false},
 	}
 	// With fixTrailingSlash = true
 	for _, test := range tests {