1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
package cask.internal
import collection.mutable
object DispatchTrie{
def construct[T](index: Int,
inputs: collection.Seq[(collection.IndexedSeq[String], T, Boolean)]): DispatchTrie[T] = {
val continuations = mutable.Map.empty[String, mutable.Buffer[(collection.IndexedSeq[String], T, Boolean)]]
val terminals = mutable.Buffer.empty[(collection.IndexedSeq[String], T, Boolean)]
for((path, endPoint, allowSubpath) <- inputs) {
if (path.length < index) () // do nothing
else if (path.length == index) {
terminals.append((path, endPoint, allowSubpath))
} else if (path.length > index){
val buf = continuations.getOrElseUpdate(path(index), mutable.Buffer.empty)
buf.append((path, endPoint, allowSubpath))
}
}
val wildcards = continuations.filter(_._1(0) == ':')
if (terminals.length > 1){
throw new Exception(
"More than one endpoint has the same path: " +
terminals.map(_._1.map(_.mkString("/"))).mkString(", ")
)
} else if(wildcards.size >= 1 && continuations.size > 1) {
throw new Exception(
"Routes overlap with wildcards: " +
(wildcards ++ continuations).flatMap(_._2).map(_._1.mkString("/"))
)
}else if (terminals.headOption.exists(_._3) && continuations.size == 1){
throw new Exception(
"Routes overlap with subpath capture: " +
(wildcards ++ continuations).flatMap(_._2).map(_._1.mkString("/"))
)
}else{
DispatchTrie[T](
current = terminals.headOption.map(x => x._2 -> x._3),
children = continuations.map{ case (k, vs) => (k, construct(index + 1, vs))}.toMap
)
}
}
}
/**
* A simple Trie that can be compiled from a list of endpoints, to allow
* endpoint lookup in O(length-of-request-path) time. Lookup returns the
* [[T]] this trie contains, as well as a map of bound wildcards (path
* segments starting with `:`) and any remaining un-used path segments
* (only when `current._2 == true`, indicating this route allows trailing
* segments)
*/
case class DispatchTrie[T](current: Option[(T, Boolean)],
children: Map[String, DispatchTrie[T]]){
final def lookup(remainingInput: List[String],
bindings: Map[String, String])
: Option[(T, Map[String, String], Seq[String])] = {
remainingInput match{
case Nil =>
current.map(x => (x._1, bindings, Nil))
case head :: rest if current.exists(_._2) =>
current.map(x => (x._1, bindings, head :: rest))
case head :: rest =>
if (children.size == 1 && children.keys.head.startsWith(":")){
children.values.head.lookup(rest, bindings + (children.keys.head.drop(1) -> head))
}else{
children.get(head) match{
case None => None
case Some(continuation) => continuation.lookup(rest, bindings)
}
}
}
}
}
|
