0001    // TrieRouteMatcher.swift
0002    //
0003    // The MIT License (MIT)
0004    //
0005    // Copyright (c) 2016 Dan Appel
0006    //
0007    // Permission is hereby granted, free of charge, to any person obtaining a copy
0008    // of this software and associated documentation files (the "Software"), to deal
0009    // in the Software without restriction, including without limitation the rights
0010    // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
0011    // copies of the Software, and to permit persons to whom the Software is
0012    // furnished to do so, subject to the following conditions:
0013    //
0014    // The above copyright notice and this permission notice shall be included in all
0015    // copies or substantial portions of the Software.
0016    //
0017    // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
0018    // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
0019    // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
0020    // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
0021    // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
0022    // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
0023    // SOFTWARE.
0024    
0025    @_exported import HTTP
0026    
0027    public struct TrieRouteMatcher
TrieRouteMatcher.swift:219
extension TrieRouteMatcher: CustomStringConvertible {: RouteMatcherType {
0028        private var componentsTrie
TrieRouteMatcher.swift:221
        return componentsTrie.description + "\n" + routesTrie.description = Trie<Character, Int>()
0029        private var routesTrie = Trie<Int, Route>()
0030        public let routes: [Route]
0031        private var parameterDictionary = [Int:String]()
0032    
0033        public init(routes: [Route]) {
0034            self.routes = routes
0035    
0036            var nextComponentId = 
0037    
0038            for route in routes {
0039                
0040                for method in route.methods {
0041                    
0042                    // add the method to the path so it is checked
0043                    let path = method.description + route.path
0044                    
0045                    // turn component (string) into an id (integer) for fast comparisons
0046                    let componentIds = path.split("/").map { component -> Int in
0047                        
0048                        // if it already has a component with the same name, use that id
0049                        if let id = componentsTrie.findPayload(component.characters) {
0050                            return id
0051                        }
0052                        
0053                        let id: Int
0054                        
0055                        if component.characters.first == ":" {
0056                            // if component is a parameter, give it a negative id
0057                            id = -nextComponentId
0058                        } else {
0059                            // normal component, give it a positive id
0060                            id = nextComponentId
0061                        }
0062    
0063                        if id <  {
0064                            // drop colon (":"), then combine characters into string
0065                            let parameter = String(component.characters.dropFirst())
0066                            parameterDictionary[id] = parameter
0067                        }
0068    
0069                        // increment id for next component
0070                        nextComponentId += 
0071                        
0072                        // insert the component into the trie with the next id
0073                        componentsTrie.insert(component.characters, payload: id)
0074                        
0075                        return id
0076                    }
0077    
0078                    // insert the components with the end node containing the route
0079                    routesTrie.insert(componentIds, payload: route)
0080                }
0081            }
0082        }
0083    
0084        func searchForRoute(head head: Trie<Int, Route>, components: [String], componentIndex startingIndex: Int, inout parameters: [String:String]) -> Route? {
0085    
0086            // topmost route node. children are searched for route matches,
0087            // if they match, that matching node gets set to head
0088            var head = head
0089    
0090            // if at any point the trie comes up with multiple options for descent, it is to
0091            // store the alternatives and the index of the component at which it found the alternative
0092            // node so that it can backtrack and search through that alternative node if the original
0093            // node ends up 404'ing
0094            var alternatives: [(Int, Trie<Int, Route>)] = []
0095    
0096            // go through the components starting at the start index. the start index can change
0097            // to be more than 0 if the trie ran into a dead-end and goes backwards (recursively) through its alternatives
0098            componentLoop: for (componentIndex, component) in components[startingIndex..<components.count].enumerate() {
0099    
0100                // search for component in the components dictionary
0101                let id = componentsTrie.findPayload(component.characters)
0102    
0103                // not found in the dictionary - either parameter or 404
0104                if id == nil {
0105    
0106                    for child in head.children {
0107    
0108                        // if the id of the route component is negative,
0109                        // it is a parameter route
0110                        if child.prefix <  {
0111                            head = child
0112                            let parameter = parameterDictionary[child.prefix!]
0113                            parameters[parameter!] = component
0114                            continue componentLoop
0115                        }
0116                    }
0117    
0118                    // no routes matches
0119                    return nil
0120                }
0121    
0122                // need to sort these in descending order, otherwise
0123                // children with negative prefixes (parameters) can take
0124                // priority over static paths (which they shouldnt)
0125                head.children.sortInPlace { n1, n2 in
0126                    n1.prefix > n2.prefix
0127                }
0128    
0129                // gets set to the first node to match. however, since we want to fill up alternatives,
0130                // we wait until we loop through all the children before descending further down the
0131                // trie through the preferredHead node
0132                var preferredHead: Trie<Int, Route>? = nil
0133    
0134                // component exists in the routes
0135                for child in head.children {
0136    
0137                    // normal, static route
0138                    if child.prefix == id {
0139                        if preferredHead == nil { preferredHead = child }
0140                        else { alternatives.append((componentIndex + , child)) }
0141                        continue
0142                    }
0143    
0144                    // still could be a parameter
0145                    // ex: route.get("/api/:version")
0146                    // request: /api/api
0147                    if child.prefix <  {
0148                        if preferredHead == nil {
0149                            preferredHead = child
0150                            let parameter = parameterDictionary[child.prefix!]
0151                            parameters[parameter!] = component
0152                        } else {
0153                            alternatives.append((componentIndex + , child))
0154                        }
0155                    }
0156                }
0157    
0158                // route was matched
0159                if let preferredHead = preferredHead {
0160                    head = preferredHead
0161                    continue
0162                }
0163    
0164                // the path we just took led to a 404. go through all alternative
0165                // paths (could be an empty array) and try those as well
0166                for alternative in alternatives {
0167    
0168                    let matched = searchForRoute(head: alternative., components: components, componentIndex: alternative., parameters: &parameters)
0169    
0170                    if matched != nil { return matched }
0171                }
0172    
0173                // 404 even after going through alternatives. no routes matched
0174                return nil
0175            }
0176    
0177            // success! found a route.
0178            return head.payload
0179        }
0180    
0181        public func match(request: Request) -> Route? {
0182            guard let path = request.path else {
0183                return nil
0184            }
0185    
0186            let components = [request.method.description] + path.unicodeScalars.split("/").map(String.init)
0187    
0188            var parameters = [String:String]()
0189    
0190            // start searching for the route from the head of the routesTrie
0191            let matched = searchForRoute(head: routesTrie, components: components, componentIndex: , parameters: &parameters)
0192    
0193            // ensure the route was found
0194            guard let route = matched else { return nil }
0195    
0196            // no parameters? no problem
0197            if parameters.isEmpty {
0198                return route
0199            }
0200    
0201            // wrap the route to inject the pathParameters upon receiving a request
0202            let wrappedRoute = Route(
0203                methods: route.methods,
0204                path: route.path,
0205                middleware: route.middleware,
0206                responder: Responder { req in
0207                    var req = req
0208                    for (key, parameter) in parameters {
0209                        req.pathParameters[key] = parameter
0210                    }
0211                    return try route.respond(req)
0212                }
0213            )
0214    
0215            return wrappedRoute
0216        }
0217    }
0218    
0219    extension TrieRouteMatcher: CustomStringConvertible {
0220        public var description: String {
0221            return componentsTrie.description + "\n" + routesTrie.description
0222        }
0223    }
0224