<commit_before>/*
 * Authored by <NAME>, 2018-2019.
 * Intellectual property of third-party.

 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at

 *     http://www.apache.org/licenses/LICENSE-2.0

 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef UWS_HTTPROUTER_HPP
#define UWS_HTTPROUTER_HPP

/* HTTP router is an independent module subject to unit testing and fuzz testing */
/* This module is not fully optimized yet, waiting for more features before doing so */

#include <map>
#include <vector>
#include <cstring>
#include <string_view>
#include <string>
#include <algorithm>
#include <memory>

#include "f2/function2.hpp"

namespace uWS {

template <class USERDATA>
struct HttpRouter {
    /* These are public for now */
    std::vector<std::string> methods = {"get", "post", "head", "put", "delete", "connect", "options", "trace", "patch"};

private:
    USERDATA userData;

    /* 32-bit handler id */
    const static uint32_t HANDLER_MASK = 0x0fffffff;
    const static uint32_t HIGH_PRIORITY = 0xd0000000;
    const static uint32_t MEDIUM_PRIORITY = 0xe0000000;
    const static uint32_t LOW_PRIORITY = 0xf0000000;

    static const unsigned int MAX_URL_SEGMENTS = 100;
    
    /* Methods and their respective priority */
    std::map<std::string, int> priority;

    /* List of handlers */
    std::vector<fu2::unique_function<bool(HttpRouter *)>> handlers;

    /* Current URL cache */
    std::string_view currentUrl;
    std::string_view urlSegmentVector[MAX_URL_SEGMENTS];
    int urlSegmentTop;

    /* The matching tree */
    struct Node {
        std::string name;
        std::vector<std::unique_ptr<Node>> children;
        std::vector<uint32_t> handlers;
    } root = {"rootNode"};

    /* Advance from parent to child, adding child if necessary */
    Node *getNode(Node *parent, std::string child) {
        for (std::unique_ptr<Node> &node : parent->children) {
            if (node->name == child) {
                return node.get();
            }
        }

        /* Insert sorted, but keep order if parent is root (we sort methods by priority elsewhere) */
        std::unique_ptr<Node> newNode(new Node({child}));
        return parent->children.emplace(std::upper_bound(parent->children.begin(), parent->children.end(), newNode, [parent, this](auto &a, auto &b) {
            return b->name.length() && (parent != &root) && (b->name < a->name);
        }), std::move(newNode))->get();
    }

    /* Basically a pre-allocated stack */
    struct RouteParameters {
        friend struct HttpRouter;
    private:
        std::string_view params[MAX_URL_SEGMENTS];
        int paramsTop;

        void reset() {
            paramsTop = -1;
        }

        void push(std::string_view param) {
            /* We check these bounds indirectly via the urlSegments limit */
            params[++paramsTop] = param;
        }

        void pop() {
            /* Same here, we cannot pop outside */
            paramsTop--;
        }
    } routeParameters;

    /* Set URL for router. Will reset any URL cache */
    inline void setUrl(std::string_view url) {
        /* Remove / from input URL */
        currentUrl = url.substr(std::min<unsigned int>((unsigned int) url.length(), 1));
        urlSegmentTop = -1;
    }

    /* Lazily parse or read from cache */
    inline std::string_view getUrlSegment(int urlSegment) {
        if (urlSegment > urlSegmentTop) {
            /* Return empty segment if we are out of URL or stack space, but never for first url segment */
            if (!currentUrl.length() || urlSegment > 99) {
                return {};
            }

            auto segmentLength = currentUrl.find('/');
            if (segmentLength == std::string::npos) {
                segmentLength = currentUrl.length();

                /* Push to url segment vector */
                urlSegmentVector[urlSegment] = currentUrl.substr(0, segmentLength);
                urlSegmentTop++;

                /* Update currentUrl */
                currentUrl = currentUrl.substr(segmentLength);
            } else {
                /* Push to url segment vector */
                urlSegmentVector[urlSegment] = currentUrl.substr(0, segmentLength);
                urlSegmentTop++;

                /* Update currentUrl */
                currentUrl = currentUrl.substr(segmentLength + 1);
            }
        }
        /* In any case we return it */
        return urlSegmentVector[urlSegment];
    }

    /* Experimental path, executes as many handlers it can */
    bool executeHandlers(Node *parent, int urlSegment, USERDATA &userData) {
        /* If we have no more URL and not on first round, return where we may stand */
        if (urlSegment && !getUrlSegment(urlSegment).length()) {
            /* We have reached accross the entire URL with no stoppage, execute */
            for (int handler : parent->handlers) {
                if (handlers[handler & HANDLER_MASK](this)) {
                    return true;
                }
            }
            /* We reached the end, so go back */
            return false;
        }

        for (auto &p : parent->children) {
            if (p->name.length() && p->name[0] == '*') {
                /* Wildcard match (can be seen as a shortcut) */
                for (int handler : p->handlers) {
                    if (handlers[handler & HANDLER_MASK](this)) {
                        return true;
                    }
                }
            } else if (p->name.length() && p->name[0] == ':' && getUrlSegment(urlSegment).length()) {
                /* Parameter match */
                routeParameters.push(getUrlSegment(urlSegment));
                if (executeHandlers(p.get(), urlSegment + 1, userData)) {
                    return true;<commit_msg>Woops, fix router<commit_after>/*
 * Authored by <NAME>, 2018-2019.
 * Intellectual property of third-party.

 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at

 *     http://www.apache.org/licenses/LICENSE-2.0

 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef UWS_HTTPROUTER_HPP
#define UWS_HTTPROUTER_HPP

#include <map>
#include <vector>
#include <cstring>
#include <string_view>
#include <string>
#include <algorithm>
#include <memory>

#include "f2/function2.hpp"

namespace uWS {

template <class USERDATA>
struct HttpRouter {
    /* These are public for now */
    std::vector<std::string> methods = {"get", "post", "head", "put", "delete", "connect", "options", "trace", "patch"};
    static const uint32_t HIGH_PRIORITY = 0xd0000000, MEDIUM_PRIORITY = 0xe0000000, LOW_PRIORITY = 0xf0000000;

private:
    USERDATA userData;
    static const unsigned int MAX_URL_SEGMENTS = 100;

    /* Handler ids are 32-bit */
    static const uint32_t HANDLER_MASK = 0x0fffffff;
    
    /* Methods and their respective priority */
    std::map<std::string, int> priority;

    /* List of handlers */
    std::vector<fu2::unique_function<bool(HttpRouter *)>> handlers;

    /* Current URL cache */
    std::string_view currentUrl;
    std::string_view urlSegmentVector[MAX_URL_SEGMENTS];
    int urlSegmentTop;

    /* The matching tree */
    struct Node {
        std::string name;
        std::vector<std::unique_ptr<Node>> children;
        std::vector<uint32_t> handlers;
    } root = {"rootNode"};

    /* Advance from parent to child, adding child if necessary */
    Node *getNode(Node *parent, std::string child) {
        for (std::unique_ptr<Node> &node : parent->children) {
            if (node->name == child) {
                return node.get();
            }
        }

        /* Insert sorted, but keep order if parent is root (we sort methods by priority elsewhere) */
        std::unique_ptr<Node> newNode(new Node({child}));
        return parent->children.emplace(std::upper_bound(parent->children.begin(), parent->children.end(), newNode, [parent, this](auto &a, auto &b) {
            return b->name.length() && (parent != &root) && (b->name < a->name);
        }), std::move(newNode))->get();
    }

    /* Basically a pre-allocated stack */
    struct RouteParameters {
        friend struct HttpRouter;
    private:
        std::string_view params[MAX_URL_SEGMENTS];
        int paramsTop;

        void reset() {
            paramsTop = -1;
        }

        void push(std::string_view param) {
            /* We check these bounds indirectly via the urlSegments limit */
            params[++paramsTop] = param;
        }

        void pop() {
            /* Same here, we cannot pop outside */
            paramsTop--;
        }
    } routeParameters;

    /* Set URL for router. Will reset any URL cache */
    inline void setUrl(std::string_view url) {
        /* Remove / from input URL */
        currentUrl = url.substr(std::min<unsigned int>((unsigned int) url.length(), 1));
        urlSegmentTop = -1;
    }

    /* Lazily parse or read from cache */
    inline std::string_view getUrlSegment(int urlSegment) {
        if (urlSegment > urlSegmentTop) {
            /* Return empty segment if we are out of URL or stack space, but never for first url segment */
            if (!currentUrl.length() || urlSegment > 99) {
                return {};
            }

            auto segmentLength = currentUrl.find('/');
            if (segmentLength == std::string::npos) {
                segmentLength = currentUrl.length();

                /* Push to url segment vector */
                urlSegmentVector[urlSegment] = currentUrl.substr(0, segmentLength);
                urlSegmentTop++;

                /* Update currentUrl */
                currentUrl = currentUrl.substr(segmentLength);
            } else {
                /* Push to url segment vector */
                urlSegmentVector[urlSegment] = currentUrl.substr(0, segmentLength);
                urlSegmentTop++;

                /* Update currentUrl */
                currentUrl = currentUrl.substr(segmentLength + 1);
            }
        }
        /* In any case we return it */
        return urlSegmentVector[urlSegment];
    }

    /* Executes as many handlers it can */
    bool executeHandlers(Node *parent, int urlSegment, USERDATA &userData) {
        /* If we have no more URL and not on first round, return where we may stand */
        if (urlSegment && !getUrlSegment(urlSegment).length()) {
            /* We have reached accross the entire URL with no stoppage, execute */
            for (int handler : parent->handlers) {
                if (handlers[handler & HANDLER_MASK](this)) {
                    return true;
                }
            }
            /* We reached the end, so go back */
            return false;
        }

        for (auto &p : parent->children) {
            if (p->name.length() && p->name[0] == '*') {
                /* Wildcard match (can be seen as a shortcut) */
                for (int handler : p->handlers) {
                    if (handlers[handler & HANDLER_MASK](this)) {
                        return true;
                    }
                }
            } else if (p->name.length() && p->name[0] == ':' && getUrlSegment(urlSegment).length()) {
                /* Parameter match */
                routeParameters.push(getUrlSegment(urlSegment));
                if (executeHandlers(p.get(), urlSegment + 1, userData)) {
                    return true;
{'fraction_non_alphanumeric': 0.11381644106965995, 'fraction_numerical': 0.01072961373390558, 'mean_word_length': 2.167843137254902, 'pattern_counts': {'":': 0, '<': 43, '<?xml version=': 0, '>': 77, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 8, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4845763', 'n_tokens_mistral': 3448, 'n_tokens_neox': 3213, 'n_words': 1029}