http/routing.hpp

#pragma once

#include "async_resp.hpp"
#include "common.hpp"
#include "dbus_privileges.hpp"
#include "dbus_utility.hpp"
#include "error_messages.hpp"
#include "http_request.hpp"
#include "http_response.hpp"
#include "logging.hpp"
#include "privileges.hpp"
#include "routing/baserule.hpp"
#include "routing/dynamicrule.hpp"
#include "routing/sserule.hpp"
#include "routing/taggedrule.hpp"
#include "routing/websocketrule.hpp"
#include "sessions.hpp"
#include "utility.hpp"
#include "utils/dbus_utils.hpp"
#include "verb.hpp"
#include "websocket.hpp"

#include <boost/beast/ssl/ssl_stream.hpp>
#include <boost/container/flat_map.hpp>
#include <boost/url/format.hpp>
#include <sdbusplus/unpack_properties.hpp>

#include <cerrno>
#include <cstdint>
#include <cstdlib>
#include <limits>
#include <memory>
#include <optional>
#include <tuple>
#include <utility>
#include <vector>

namespace crow
{

class Trie
{
  public:
    struct Node
    {
        unsigned ruleIndex{};
        std::array<size_t, static_cast<size_t>(ParamType::MAX)>
            paramChildrens{};
        using ChildMap = boost::container::flat_map<
            std::string, unsigned, std::less<>,
            std::vector<std::pair<std::string, unsigned>>>;
        ChildMap children;

        bool isSimpleNode() const
        {
            return ruleIndex == 0 &&
                   std::all_of(std::begin(paramChildrens),
                               std::end(paramChildrens),
                               [](size_t x) { return x == 0U; });
        }
    };

    Trie() : nodes(1) {}

  private:
    void optimizeNode(Node* node)
    {
        for (size_t x : node->paramChildrens)
        {
            if (x == 0U)
            {
                continue;
            }
            Node* child = &nodes[x];
            optimizeNode(child);
        }
        if (node->children.empty())
        {
            return;
        }
        bool mergeWithChild = true;
        for (const Node::ChildMap::value_type& kv : node->children)
        {
            Node* child = &nodes[kv.second];
            if (!child->isSimpleNode())
            {
                mergeWithChild = false;
                break;
            }
        }
        if (mergeWithChild)
        {
            Node::ChildMap merged;
            for (const Node::ChildMap::value_type& kv : node->children)
            {
                Node* child = &nodes[kv.second];
                for (const Node::ChildMap::value_type& childKv :
                     child->children)
                {
                    merged[kv.first + childKv.first] = childKv.second;
                }
            }
            node->children = std::move(merged);
            optimizeNode(node);
        }
        else
        {
            for (const Node::ChildMap::value_type& kv : node->children)
            {
                Node* child = &nodes[kv.second];
                optimizeNode(child);
            }
        }
    }

    void optimize()
    {
        optimizeNode(head());
    }

  public:
    void validate()
    {
        optimize();
    }

    void findRouteIndexes(const std::string& reqUrl,
                          std::vector<unsigned>& routeIndexes,
                          const Node* node = nullptr, unsigned pos = 0) const
    {
        if (node == nullptr)
        {
            node = head();
        }
        for (const Node::ChildMap::value_type& kv : node->children)
        {
            const std::string& fragment = kv.first;
            const Node* child = &nodes[kv.second];
            if (pos >= reqUrl.size())
            {
                if (child->ruleIndex != 0 && fragment != "/")
                {
                    routeIndexes.push_back(child->ruleIndex);
                }
                findRouteIndexes(reqUrl, routeIndexes, child,
                                 static_cast<unsigned>(pos + fragment.size()));
            }
            else
            {
                if (reqUrl.compare(pos, fragment.size(), fragment) == 0)
                {
                    findRouteIndexes(
                        reqUrl, routeIndexes, child,
                        static_cast<unsigned>(pos + fragment.size()));
                }
            }
        }
    }

    std::pair<unsigned, std::vector<std::string>>
        find(const std::string_view reqUrl, const Node* node = nullptr,
             size_t pos = 0, std::vector<std::string>* params = nullptr) const
    {
        std::vector<std::string> empty;
        if (params == nullptr)
        {
            params = &empty;
        }

        unsigned found{};
        std::vector<std::string> matchParams;

        if (node == nullptr)
        {
            node = head();
        }
        if (pos == reqUrl.size())
        {
            return {node->ruleIndex, *params};
        }

        auto updateFound =
            [&found,
             &matchParams](std::pair<unsigned, std::vector<std::string>>& ret) {
            if (ret.first != 0U && (found == 0U || found > ret.first))
            {
                found = ret.first;
                matchParams = std::move(ret.second);
            }
        };

        if (node->paramChildrens[static_cast<size_t>(ParamType::STRING)] != 0U)
        {
            size_t epos = pos;
            for (; epos < reqUrl.size(); epos++)
            {
                if (reqUrl[epos] == '/')
                {
                    break;
                }
            }

            if (epos != pos)
            {
                params->emplace_back(reqUrl.substr(pos, epos - pos));
                std::pair<unsigned, std::vector<std::string>> ret =
                    find(reqUrl,
                         &nodes[node->paramChildrens[static_cast<size_t>(
                             ParamType::STRING)]],
                         epos, params);
                updateFound(ret);
                params->pop_back();
            }
        }

        if (node->paramChildrens[static_cast<size_t>(ParamType::PATH)] != 0U)
        {
            size_t epos = reqUrl.size();

            if (epos != pos)
            {
                params->emplace_back(reqUrl.substr(pos, epos - pos));
                std::pair<unsigned, std::vector<std::string>> ret =
                    find(reqUrl,
                         &nodes[node->paramChildrens[static_cast<size_t>(
                             ParamType::PATH)]],
                         epos, params);
                updateFound(ret);
                params->pop_back();
            }
        }

        for (const Node::ChildMap::value_type& kv : node->children)
        {
            const std::string& fragment = kv.first;
            const Node* child = &nodes[kv.second];

            if (reqUrl.compare(pos, fragment.size(), fragment) == 0)
            {
                std::pair<unsigned, std::vector<std::string>> ret =
                    find(reqUrl, child, pos + fragment.size(), params);
                updateFound(ret);
            }
        }

        return {found, matchParams};
    }

    void add(const std::string& url, unsigned ruleIndex)
    {
        size_t idx = 0;

        for (unsigned i = 0; i < url.size(); i++)
        {
            char c = url[i];
            if (c == '<')
            {
                constexpr static std::array<
                    std::pair<ParamType, std::string_view>, 3>
                    paramTraits = {{
                        {ParamType::STRING, "<str>"},
                        {ParamType::STRING, "<string>"},
                        {ParamType::PATH, "<path>"},
                    }};

                for (const std::pair<ParamType, std::string_view>& x :
                     paramTraits)
                {
                    if (url.compare(i, x.second.size(), x.second) == 0)
                    {
                        size_t index = static_cast<size_t>(x.first);
                        if (nodes[idx].paramChildrens[index] == 0U)
                        {
                            unsigned newNodeIdx = newNode();
                            nodes[idx].paramChildrens[index] = newNodeIdx;
                        }
                        idx = nodes[idx].paramChildrens[index];
                        i += static_cast<unsigned>(x.second.size());
                        break;
                    }
                }

                i--;
            }
            else
            {
                std::string piece(&c, 1);
                if (nodes[idx].children.count(piece) == 0U)
                {
                    unsigned newNodeIdx = newNode();
                    nodes[idx].children.emplace(piece, newNodeIdx);
                }
                idx = nodes[idx].children[piece];
            }
        }
        if (nodes[idx].ruleIndex != 0U)
        {
            throw std::runtime_error("handler already exists for " + url);
        }
        nodes[idx].ruleIndex = ruleIndex;
    }

  private:
    void debugNodePrint(Node* n, size_t level)
    {
        for (size_t i = 0; i < static_cast<size_t>(ParamType::MAX); i++)
        {
            if (n->paramChildrens[i] != 0U)
            {
                BMCWEB_LOG_DEBUG << std::string(
                    2U * level, ' ') /*<< "("<<n->paramChildrens[i]<<") "*/;
                switch (static_cast<ParamType>(i))
                {
                    case ParamType::STRING:
                        BMCWEB_LOG_DEBUG << "<str>";
                        break;
                    case ParamType::PATH:
                        BMCWEB_LOG_DEBUG << "<path>";
                        break;
                    case ParamType::MAX:
                        BMCWEB_LOG_DEBUG << "<ERROR>";
                        break;
                }

                debugNodePrint(&nodes[n->paramChildrens[i]], level + 1);
            }
        }
        for (const Node::ChildMap::value_type& kv : n->children)
        {
            BMCWEB_LOG_DEBUG
                << std::string(2U * level, ' ') /*<< "(" << kv.second << ") "*/
                << kv.first;
            debugNodePrint(&nodes[kv.second], level + 1);
        }
    }

  public:
    void debugPrint()
    {
        debugNodePrint(head(), 0U);
    }

  private:
    const Node* head() const
    {
        return &nodes.front();
    }

    Node* head()
    {
        return &nodes.front();
    }

    unsigned newNode()
    {
        nodes.resize(nodes.size() + 1);
        return static_cast<unsigned>(nodes.size() - 1);
    }

    std::vector<Node> nodes;
};

class Router
{
  public:
    Router() = default;

    DynamicRule& newRuleDynamic(const std::string& rule)
    {
        std::unique_ptr<DynamicRule> ruleObject =
            std::make_unique<DynamicRule>(rule);
        DynamicRule* ptr = ruleObject.get();
        allRules.emplace_back(std::move(ruleObject));

        return *ptr;
    }

    template <uint64_t N>
    typename black_magic::Arguments<N>::type::template rebind<TaggedRule>&
        newRuleTagged(const std::string& rule)
    {
        using RuleT = typename black_magic::Arguments<N>::type::template rebind<
            TaggedRule>;
        std::unique_ptr<RuleT> ruleObject = std::make_unique<RuleT>(rule);
        RuleT* ptr = ruleObject.get();
        allRules.emplace_back(std::move(ruleObject));

        return *ptr;
    }

    void internalAddRuleObject(const std::string& rule, BaseRule* ruleObject)
    {
        if (ruleObject == nullptr)
        {
            return;
        }
        for (size_t method = 0, methodBit = 1; method <= methodNotAllowedIndex;
             method++, methodBit <<= 1)
        {
            if ((ruleObject->methodsBitfield & methodBit) > 0U)
            {
                perMethods[method].rules.emplace_back(ruleObject);
                perMethods[method].trie.add(
                    rule, static_cast<unsigned>(
                              perMethods[method].rules.size() - 1U));
                // directory case:
                //   request to `/about' url matches `/about/' rule
                if (rule.size() > 2 && rule.back() == '/')
                {
                    perMethods[method].trie.add(
                        rule.substr(0, rule.size() - 1),
                        static_cast<unsigned>(perMethods[method].rules.size() -
                                              1));
                }
            }
        }
    }

    void validate()
    {
        for (std::unique_ptr<BaseRule>& rule : allRules)
        {
            if (rule)
            {
                std::unique_ptr<BaseRule> upgraded = rule->upgrade();
                if (upgraded)
                {
                    rule = std::move(upgraded);
                }
                rule->validate();
                internalAddRuleObject(rule->rule, rule.get());
            }
        }
        for (PerMethod& perMethod : perMethods)
        {
            perMethod.trie.validate();
        }
    }

    struct FindRoute
    {
        BaseRule* rule = nullptr;
        std::vector<std::string> params;
    };

    struct FindRouteResponse
    {
        std::string allowHeader;
        FindRoute route;
    };

    FindRoute findRouteByIndex(std::string_view url, size_t index) const
    {
        FindRoute route;
        if (index >= perMethods.size())
        {
            BMCWEB_LOG_CRITICAL << "Bad index???";
            return route;
        }
        const PerMethod& perMethod = perMethods[index];
        std::pair<unsigned, std::vector<std::string>> found =
            perMethod.trie.find(url);
        if (found.first >= perMethod.rules.size())
        {
            throw std::runtime_error("Trie internal structure corrupted!");
        }
        // Found a 404 route, switch that in
        if (found.first != 0U)
        {
            route.rule = perMethod.rules[found.first];
            route.params = std::move(found.second);
        }
        return route;
    }

    FindRouteResponse findRoute(Request& req) const
    {
        FindRouteResponse findRoute;

        std::optional<HttpVerb> verb = httpVerbFromBoost(req.method());
        if (!verb)
        {
            return findRoute;
        }
        size_t reqMethodIndex = static_cast<size_t>(*verb);
        // Check to see if this url exists at any verb
        for (size_t perMethodIndex = 0; perMethodIndex <= maxVerbIndex;
             perMethodIndex++)
        {
            // Make sure it's safe to deference the array at that index
            static_assert(maxVerbIndex <
                          std::tuple_size_v<decltype(perMethods)>);
            FindRoute route = findRouteByIndex(req.url().encoded_path(),
                                               perMethodIndex);
            if (route.rule == nullptr)
            {
                continue;
            }
            if (!findRoute.allowHeader.empty())
            {
                findRoute.allowHeader += ", ";
            }
            HttpVerb thisVerb = static_cast<HttpVerb>(perMethodIndex);
            findRoute.allowHeader += httpVerbToString(thisVerb);
            if (perMethodIndex == reqMethodIndex)
            {
                findRoute.route = route;
            }
        }
        return findRoute;
    }

    template <typename Adaptor>
    void handleUpgrade(Request& req,
                       const std::shared_ptr<bmcweb::AsyncResp>& asyncResp,
                       Adaptor&& adaptor)
    {
        std::optional<HttpVerb> verb = httpVerbFromBoost(req.method());
        if (!verb || static_cast<size_t>(*verb) >= perMethods.size())
        {
            asyncResp->res.result(boost::beast::http::status::not_found);
            return;
        }
        PerMethod& perMethod = perMethods[static_cast<size_t>(*verb)];
        Trie& trie = perMethod.trie;
        std::vector<BaseRule*>& rules = perMethod.rules;

        const std::pair<unsigned, std::vector<std::string>>& found =
            trie.find(req.url().encoded_path());
        unsigned ruleIndex = found.first;
        if (ruleIndex == 0U)
        {
            BMCWEB_LOG_DEBUG << "Cannot match rules "
                             << req.url().encoded_path();
            asyncResp->res.result(boost::beast::http::status::not_found);
            return;
        }

        if (ruleIndex >= rules.size())
        {
            throw std::runtime_error("Trie internal structure corrupted!");
        }

        BaseRule& rule = *rules[ruleIndex];
        size_t methods = rule.getMethods();
        if ((methods & (1U << static_cast<size_t>(*verb))) == 0)
        {
            BMCWEB_LOG_DEBUG
                << "Rule found but method mismatch: "
                << req.url().encoded_path() << " with " << req.methodString()
                << "(" << static_cast<uint32_t>(*verb) << ") / " << methods;
            asyncResp->res.result(boost::beast::http::status::not_found);
            return;
        }

        BMCWEB_LOG_DEBUG << "Matched rule (upgrade) '" << rule.rule << "' "
                         << static_cast<uint32_t>(*verb) << " / " << methods;

        // TODO(ed) This should be able to use std::bind_front, but it doesn't
        // appear to work with the std::move on adaptor.
        validatePrivilege(
            req, asyncResp, rule,
            [&rule, asyncResp, adaptor(std::forward<Adaptor>(adaptor))](
                Request& thisReq) mutable {
            rule.handleUpgrade(thisReq, asyncResp, std::move(adaptor));
            });
    }

    void handle(Request& req,
                const std::shared_ptr<bmcweb::AsyncResp>& asyncResp)
    {
        std::optional<HttpVerb> verb = httpVerbFromBoost(req.method());
        if (!verb || static_cast<size_t>(*verb) >= perMethods.size())
        {
            asyncResp->res.result(boost::beast::http::status::not_found);
            return;
        }

        FindRouteResponse foundRoute = findRoute(req);

        if (foundRoute.route.rule == nullptr)
        {
            // Couldn't find a normal route with any verb, try looking for a 404
            // route
            if (foundRoute.allowHeader.empty())
            {
                foundRoute.route = findRouteByIndex(req.url().encoded_path(),
                                                    notFoundIndex);
            }
            else
            {
                // See if we have a method not allowed (405) handler
                foundRoute.route = findRouteByIndex(req.url().encoded_path(),
                                                    methodNotAllowedIndex);
            }
        }

        // Fill in the allow header if it's valid
        if (!foundRoute.allowHeader.empty())
        {
            asyncResp->res.addHeader(boost::beast::http::field::allow,
                                     foundRoute.allowHeader);
        }

        // If we couldn't find a real route or a 404 route, return a generic
        // response
        if (foundRoute.route.rule == nullptr)
        {
            if (foundRoute.allowHeader.empty())
            {
                asyncResp->res.result(boost::beast::http::status::not_found);
            }
            else
            {
                asyncResp->res.result(
                    boost::beast::http::status::method_not_allowed);
            }
            return;
        }

        BaseRule& rule = *foundRoute.route.rule;
        std::vector<std::string> params = std::move(foundRoute.route.params);

        BMCWEB_LOG_DEBUG << "Matched rule '" << rule.rule << "' "
                         << static_cast<uint32_t>(*verb) << " / "
                         << rule.getMethods();

        if (req.session == nullptr)
        {
            rule.handle(req, asyncResp, params);
            return;
        }
        validatePrivilege(req, asyncResp, rule,
                          [&rule, asyncResp, params](Request& thisReq) mutable {
            rule.handle(thisReq, asyncResp, params);
        });
    }

    void debugPrint()
    {
        for (size_t i = 0; i < perMethods.size(); i++)
        {
            BMCWEB_LOG_DEBUG << boost::beast::http::to_string(
                static_cast<boost::beast::http::verb>(i));
            perMethods[i].trie.debugPrint();
        }
    }

    std::vector<const std::string*> getRoutes(const std::string& parent)
    {
        std::vector<const std::string*> ret;

        for (const PerMethod& pm : perMethods)
        {
            std::vector<unsigned> x;
            pm.trie.findRouteIndexes(parent, x);
            for (unsigned index : x)
            {
                ret.push_back(&pm.rules[index]->rule);
            }
        }
        return ret;
    }

  private:
    struct PerMethod
    {
        std::vector<BaseRule*> rules;
        Trie trie;
        // rule index 0 has special meaning; preallocate it to avoid
        // duplication.
        PerMethod() : rules(1) {}
    };

    std::array<PerMethod, methodNotAllowedIndex + 1> perMethods;
    std::vector<std::unique_ptr<BaseRule>> allRules;
};
} // namespace crow