Coverage Report

Created: 2024-04-25 06:10

/src/uWebSockets/src/HttpRouter.h
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Authored by Alex Hultman, 2018-2020.
3
 * Intellectual property of third-party.
4
5
 * Licensed under the Apache License, Version 2.0 (the "License");
6
 * you may not use this file except in compliance with the License.
7
 * You may obtain a copy of the License at
8
9
 *     http://www.apache.org/licenses/LICENSE-2.0
10
11
 * Unless required by applicable law or agreed to in writing, software
12
 * distributed under the License is distributed on an "AS IS" BASIS,
13
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14
 * See the License for the specific language governing permissions and
15
 * limitations under the License.
16
 */
17
18
#ifndef UWS_HTTPROUTER_HPP
19
#define UWS_HTTPROUTER_HPP
20
21
#include <map>
22
#include <vector>
23
#include <cstring>
24
#include <string_view>
25
#include <string>
26
#include <algorithm>
27
#include <memory>
28
#include <utility>
29
30
#include <iostream>
31
32
#include "MoveOnlyFunction.h"
33
34
namespace uWS {
35
36
template <class USERDATA>
37
struct HttpRouter {
38
    static constexpr std::string_view ANY_METHOD_TOKEN = "*";
39
    static const uint32_t HIGH_PRIORITY = 0xd0000000, MEDIUM_PRIORITY = 0xe0000000, LOW_PRIORITY = 0xf0000000;
40
41
private:
42
    USERDATA userData;
43
    static const unsigned int MAX_URL_SEGMENTS = 100;
44
45
    /* Handler ids are 32-bit */
46
    static const uint32_t HANDLER_MASK = 0x0fffffff;
47
48
    /* List of handlers */
49
    std::vector<MoveOnlyFunction<bool(HttpRouter *)>> handlers;
50
51
    /* Current URL cache */
52
    std::string_view currentUrl;
53
    std::string_view urlSegmentVector[MAX_URL_SEGMENTS];
54
    int urlSegmentTop;
55
56
    /* The matching tree */
57
    struct Node {
58
        std::string name;
59
        std::vector<std::unique_ptr<Node>> children;
60
        std::vector<uint32_t> handlers;
61
        bool isHighPriority;
62
63
70.5k
        Node(std::string name) : name(name) {}
64
    } root = {"rootNode"};
65
66
    /* Sort wildcards after alphanum */
67
25.6k
    int lexicalOrder(std::string &name) {
68
25.6k
        if (!name.length()) {
69
0
            return 2;
70
0
        }
71
25.6k
        if (name[0] == ':') {
72
6.41k
            return 1;
73
6.41k
        }
74
19.2k
        if (name[0] == '*') {
75
12.8k
            return 0;
76
12.8k
        }
77
6.41k
        return 2;
78
19.2k
    }
79
80
    /* Advance from parent to child, adding child if necessary */
81
89.7k
    Node *getNode(Node *parent, std::string child, bool isHighPriority) {
82
89.7k
        for (std::unique_ptr<Node> &node : parent->children) {
83
83.3k
            if (node->name == child && node->isHighPriority == isHighPriority) {
84
25.6k
                return node.get();
85
25.6k
            }
86
83.3k
        }
87
88
        /* Insert sorted, but keep order if parent is root (we sort methods by priority elsewhere) */
89
64.1k
        std::unique_ptr<Node> newNode(new Node(child));
90
64.1k
        newNode->isHighPriority = isHighPriority;
91
64.1k
        return parent->children.emplace(std::upper_bound(parent->children.begin(), parent->children.end(), newNode, [parent, this](auto &a, auto &b) {
92
93
38.4k
            if (a->isHighPriority != b->isHighPriority) {
94
12.8k
                return a->isHighPriority;
95
12.8k
            }
96
97
25.6k
            return b->name.length() && (parent != &root) && (lexicalOrder(b->name) < lexicalOrder(a->name));
98
38.4k
        }), std::move(newNode))->get();
99
89.7k
    }
100
101
    /* Basically a pre-allocated stack */
102
    struct RouteParameters {
103
        friend struct HttpRouter;
104
    private:
105
        std::string_view params[MAX_URL_SEGMENTS];
106
        int paramsTop;
107
108
60.2k
        void reset() {
109
60.2k
            paramsTop = -1;
110
60.2k
        }
111
112
3.70k
        void push(std::string_view param) {
113
            /* We check these bounds indirectly via the urlSegments limit */
114
3.70k
            params[++paramsTop] = param;
115
3.70k
        }
116
117
1.68k
        void pop() {
118
            /* Same here, we cannot pop outside */
119
1.68k
            paramsTop--;
120
1.68k
        }
121
    } routeParameters;
122
123
    /* Set URL for router. Will reset any URL cache */
124
124k
    inline void setUrl(std::string_view url) {
125
126
        /* Todo: URL may also start with "http://domain/" or "*", not only "/" */
127
128
        /* We expect to stand on a slash */
129
124k
        currentUrl = url;
130
124k
        urlSegmentTop = -1;
131
124k
    }
132
133
    /* Lazily parse or read from cache */
134
245k
    inline std::pair<std::string_view, bool> getUrlSegment(int urlSegment) {
135
245k
        if (urlSegment > urlSegmentTop) {
136
            /* Signal as STOP when we have no more URL or stack space */
137
175k
            if (!currentUrl.length() || urlSegment > int(MAX_URL_SEGMENTS - 1)) {
138
42.1k
                return {{}, true};
139
42.1k
            }
140
141
            /* We always stand on a slash here, so step over it */
142
133k
            currentUrl.remove_prefix(1);
143
144
133k
            auto segmentLength = currentUrl.find('/');
145
133k
            if (segmentLength == std::string::npos) {
146
114k
                segmentLength = currentUrl.length();
147
148
                /* Push to url segment vector */
149
114k
                urlSegmentVector[urlSegment] = currentUrl.substr(0, segmentLength);
150
114k
                urlSegmentTop++;
151
152
                /* Update currentUrl */
153
114k
                currentUrl = currentUrl.substr(segmentLength);
154
114k
            } else {
155
                /* Push to url segment vector */
156
18.3k
                urlSegmentVector[urlSegment] = currentUrl.substr(0, segmentLength);
157
18.3k
                urlSegmentTop++;
158
159
                /* Update currentUrl */
160
18.3k
                currentUrl = currentUrl.substr(segmentLength);
161
18.3k
            }
162
133k
        }
163
        /* In any case we return it */
164
203k
        return {urlSegmentVector[urlSegment], false};
165
245k
    }
166
167
    /* Executes as many handlers it can */
168
66.3k
    bool executeHandlers(Node *parent, int urlSegment, USERDATA &userData) {
169
170
66.3k
        auto [segment, isStop] = getUrlSegment(urlSegment);
171
172
        /* If we are on STOP, return where we may stand */
173
66.3k
        if (isStop) {
174
            /* We have reached accross the entire URL with no stoppage, execute */
175
3.70k
            for (uint32_t handler : parent->handlers) {
176
2.02k
                if (handlers[handler & HANDLER_MASK](this)) {
177
1.08k
                    return true;
178
1.08k
                }
179
2.02k
            }
180
            /* We reached the end, so go back */
181
2.62k
            return false;
182
3.70k
        }
183
184
124k
        for (auto &p : parent->children) {
185
124k
            if (p->name.length() && p->name[0] == '*') {
186
                /* Wildcard match (can be seen as a shortcut) */
187
68.9k
                for (uint32_t handler : p->handlers) {
188
68.9k
                    if (handlers[handler & HANDLER_MASK](this)) {
189
59.1k
                        return true;
190
59.1k
                    }
191
68.9k
                }
192
68.9k
            } else if (p->name.length() && p->name[0] == ':' && segment.length()) {
193
                /* Parameter match */
194
3.70k
                routeParameters.push(segment);
195
3.70k
                if (executeHandlers(p.get(), urlSegment + 1, userData)) {
196
2.02k
                    return true;
197
2.02k
                }
198
1.68k
                routeParameters.pop();
199
52.2k
            } else if (p->name == segment) {
200
                /* Static match */
201
2.38k
                if (executeHandlers(p.get(), urlSegment + 1, userData)) {
202
1.08k
                    return true;
203
1.08k
                }
204
2.38k
            }
205
124k
        }
206
364
        return false;
207
62.6k
    }
208
209
    /* Scans for one matching handler, returning the handler and its priority or UINT32_MAX for not found */
210
38.4k
    uint32_t findHandler(std::string method, std::string pattern, uint32_t priority) {
211
57.7k
        for (std::unique_ptr<Node> &node : root.children) {
212
57.7k
            if (method == node->name) {
213
25.6k
                setUrl(pattern);
214
25.6k
                Node *n = node.get();
215
25.6k
                for (int i = 0; !getUrlSegment(i).second; i++) {
216
                    /* Go to next segment or quit */
217
25.6k
                    std::string segment = std::string(getUrlSegment(i).first);
218
25.6k
                    Node *next = nullptr;
219
25.6k
                    for (std::unique_ptr<Node> &child : n->children) {
220
25.6k
                        if (child->name == segment && child->isHighPriority == (priority == HIGH_PRIORITY)) {
221
0
                            next = child.get();
222
0
                            break;
223
0
                        }
224
25.6k
                    }
225
25.6k
                    if (!next) {
226
25.6k
                        return UINT32_MAX;
227
25.6k
                    }
228
0
                    n = next;
229
0
                }
230
                /* Seek for a priority match in the found node */
231
0
                for (unsigned int i = 0; i < n->handlers.size(); i++) {
232
0
                    if ((n->handlers[i] & ~HANDLER_MASK) == priority) {
233
0
                        return n->handlers[i];
234
0
                    }
235
0
                }
236
0
                return UINT32_MAX;
237
0
            }
238
57.7k
        }
239
12.8k
        return UINT32_MAX;
240
38.4k
    }
241
242
public:
243
6.41k
    HttpRouter() {
244
        /* Always have ANY route */
245
6.41k
        getNode(&root, std::string(ANY_METHOD_TOKEN.data(), ANY_METHOD_TOKEN.length()), false);
246
6.41k
    }
247
248
70.9k
    std::pair<int, std::string_view *> getParameters() {
249
70.9k
        return {routeParameters.paramsTop, routeParameters.params};
250
70.9k
    }
251
252
131k
    USERDATA &getUserData() {
253
131k
        return userData;
254
131k
    }
255
256
    /* Fast path */
257
60.2k
    bool route(std::string_view method, std::string_view url) {
258
        /* Reset url parsing cache */
259
60.2k
        setUrl(url);
260
60.2k
        routeParameters.reset();
261
262
        /* Begin by finding the method node */
263
76.7k
        for (auto &p : root.children) {
264
76.7k
            if (p->name == method) {
265
                /* Then route the url */
266
54.2k
                if (executeHandlers(p.get(), 0, userData)) {
267
54.2k
                    return true;
268
54.2k
                } else {
269
0
                    break;
270
0
                }
271
54.2k
            }
272
76.7k
        }
273
274
        /* Always test any route last */
275
6.06k
        return executeHandlers(root.children.back().get(), 0, userData);
276
60.2k
    }
277
278
    /* Adds the corresponding entires in matching tree and handler list */
279
38.4k
    void add(std::vector<std::string> methods, std::string pattern, MoveOnlyFunction<bool(HttpRouter *)> &&handler, uint32_t priority = MEDIUM_PRIORITY) {
280
        /* First remove existing handler */
281
38.4k
        remove(methods[0], pattern, priority);
282
        
283
38.4k
        for (std::string method : methods) {
284
            /* Lookup method */
285
38.4k
            Node *node = getNode(&root, method, false);
286
            /* Iterate over all segments */
287
38.4k
            setUrl(pattern);
288
83.3k
            for (int i = 0; !getUrlSegment(i).second; i++) {
289
44.8k
                std::string strippedSegment(getUrlSegment(i).first);
290
44.8k
                if (strippedSegment.length() && strippedSegment[0] == ':') {
291
                    /* Parameter routes must be named only : */
292
6.41k
                    strippedSegment = ":";
293
6.41k
                }
294
44.8k
                node = getNode(node, strippedSegment, priority == HIGH_PRIORITY);
295
44.8k
            }
296
            /* Insert handler in order sorted by priority (most significant 1 byte) */
297
38.4k
            node->handlers.insert(std::upper_bound(node->handlers.begin(), node->handlers.end(), (uint32_t) (priority | handlers.size())), (uint32_t) (priority | handlers.size()));
298
38.4k
        }
299
300
        /* Alloate this handler */
301
38.4k
        handlers.emplace_back(std::move(handler));
302
303
        /* ANY method must be last, GET must be first */
304
57.7k
        std::sort(root.children.begin(), root.children.end(), [](const auto &a, const auto &b) {
305
            /* Assuming the list of methods is unique, non-repeating */
306
57.7k
            if (a->name == "GET") {
307
6.41k
                return true;
308
51.3k
            } else if (b->name == "GET") {
309
32.0k
                return false;
310
32.0k
            } else if (a->name == ANY_METHOD_TOKEN) {
311
12.8k
                return false;
312
12.8k
            } else if (b->name == ANY_METHOD_TOKEN) {
313
6.41k
                return true;
314
6.41k
            } else {
315
0
                return a->name < b->name;
316
0
            }
317
57.7k
        });
318
38.4k
    }
319
320
0
    bool cullNode(Node *parent, Node *node, uint32_t handler) {
321
        /* For all children */
322
0
        for (unsigned int i = 0; i < node->children.size(); ) {
323
            /* Optimization todo: only enter those with same isHighPrioirty */
324
            /* Enter child so we get depth first */
325
0
            if (!cullNode(node, node->children[i].get(), handler)) {
326
                /* Only increase if this node was not removed */
327
0
                i++;
328
0
            }
329
0
        }
330
331
        /* Cull this node (but skip the root node) */
332
0
        if (parent /*&& parent != &root*/) {
333
            /* Scan for equal (remove), greater (lower by 1) */
334
0
            for (auto it = node->handlers.begin(); it != node->handlers.end(); ) {
335
0
                if ((*it & HANDLER_MASK) > (handler & HANDLER_MASK)) {
336
0
                    *it = ((*it & HANDLER_MASK) - 1) | (*it & ~HANDLER_MASK);
337
0
                } else if (*it == handler) {
338
0
                    it = node->handlers.erase(it);
339
0
                    continue;
340
0
                }
341
0
                it++;
342
0
            }
343
344
            /* If we have no children and no handlers, remove us from the parent->children list */
345
0
            if (!node->handlers.size() && !node->children.size()) {
346
0
                parent->children.erase(std::find_if(parent->children.begin(), parent->children.end(), [node](const std::unique_ptr<Node> &a) {
347
0
                    return a.get() == node;
348
0
                }));
349
                /* Returning true means we removed node from parent */
350
0
                return true;
351
0
            }
352
0
        }
353
354
0
        return false;
355
0
    }
356
357
    /* Removes ALL routes with the same handler as can be found with the given parameters.
358
     * Removing a wildcard is done by removing ONE OF the methods the wildcard would match with.
359
     * Example: If wildcard includes POST, GET, PUT, you can remove ALL THREE by removing GET. */
360
38.4k
    void remove(std::string method, std::string pattern, uint32_t priority) {
361
38.4k
        uint32_t handler = findHandler(method, pattern, priority);
362
38.4k
        if (handler == UINT32_MAX) {
363
            /* Not found or already removed, do nothing */
364
38.4k
            return;
365
38.4k
        }
366
367
        /* Cull the entire tree */
368
        /* For all nodes in depth first tree traveral;
369
         * if node contains handler - remove the handler -
370
         * if node holds no handlers after removal, remove the node and return */
371
0
        cullNode(nullptr, &root, handler);
372
373
        /* Now remove the actual handler */
374
0
        handlers.erase(handlers.begin() + (handler & HANDLER_MASK));
375
0
    }
376
};
377
378
}
379
380
#endif // UWS_HTTPROUTER_HPP