Simplify router

Now that we only support string types in the router we no longer need to
build a "Tag" to be used for constructing argument types.  Now, we can
just track the number of arguments, which simplifies the code
significantly, and removes the need to convert to and from the tag to
parameter counts.

This in turn deletes a lot of code in the router, removing the need for
tracking tag types.

Tested: Redfish service validator passes.  Unit tests pass.

Change-Id: Ide1d665dc1984552681e8c05952b38073d5e32dd
Signed-off-by: Ed Tanous <ed@tanous.net>

4 files changed, 174 insertions, 267 deletions

diff --git a/http/common.hpp b/http/common.hpp
deleted file mode 100644
index 8fc9bcf759..0000000000
--- a/http/common.hpp
+++ /dev/null
@@ -1,23 +0,0 @@
-#pragma once
-
-#include "utility.hpp"
-
-#include <boost/beast/http/verb.hpp>
-
-#include <iostream>
-#include <stdexcept>
-#include <string>
-#include <vector>
-
-namespace crow
-{
-
-enum class ParamType
-{
-    STRING,
-    PATH,
-
-    MAX
-};
-
-} // namespace crow
diff --git a/http/http_request.hpp b/http/http_request.hpp
index d041b82660..d1a6ac053a 100644
--- a/http/http_request.hpp
+++ b/http/http_request.hpp
@@ -1,6 +1,5 @@
 #pragma once
 
-#include "common.hpp"
 #include "http_body.hpp"
 #include "sessions.hpp"
 
diff --git a/http/routing.hpp b/http/routing.hpp
index a9884667d0..fa6db58bfc 100644
--- a/http/routing.hpp
+++ b/http/routing.hpp
@@ -1,7 +1,6 @@
 #pragma once
 
 #include "async_resp.hpp"
-#include "common.hpp"
 #include "dbus_privileges.hpp"
 #include "dbus_utility.hpp"
 #include "error_messages.hpp"
@@ -20,11 +19,10 @@
 #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 <boost/container/small_vector.hpp>
 
+#include <algorithm>
 #include <cerrno>
 #include <cstdint>
 #include <cstdlib>
@@ -43,74 +41,74 @@ class Trie
   public:
     struct Node
     {
-        unsigned ruleIndex{};
-        std::array<size_t, static_cast<size_t>(ParamType::MAX)>
-            paramChildrens{};
+        unsigned ruleIndex = 0U;
+
+        size_t stringParamChild = 0U;
+        size_t pathParamChild = 0U;
+
         using ChildMap = boost::container::flat_map<
             std::string, unsigned, std::less<>,
-            std::vector<std::pair<std::string, unsigned>>>;
+            boost::container::small_vector<std::pair<std::string, unsigned>,
+                                           1>>;
         ChildMap children;
 
         bool isSimpleNode() const
         {
-            return ruleIndex == 0 &&
-                   std::all_of(std::begin(paramChildrens),
-                               std::end(paramChildrens),
-                               [](size_t x) { return x == 0U; });
+            return ruleIndex == 0 && stringParamChild == 0 &&
+                   pathParamChild == 0;
         }
     };
 
     Trie() : nodes(1) {}
 
   private:
-    void optimizeNode(Node* node)
+    void optimizeNode(Node& node)
     {
-        for (size_t x : node->paramChildrens)
+        if (node.stringParamChild != 0U)
         {
-            if (x == 0U)
-            {
-                continue;
-            }
-            Node* child = &nodes[x];
-            optimizeNode(child);
+            optimizeNode(nodes[node.stringParamChild]);
         }
-        if (node->children.empty())
+        if (node.pathParamChild != 0U)
         {
-            return;
+            optimizeNode(nodes[node.pathParamChild]);
         }
-        bool mergeWithChild = true;
-        for (const Node::ChildMap::value_type& kv : node->children)
+
+        if (node.children.empty())
         {
-            Node* child = &nodes[kv.second];
-            if (!child->isSimpleNode())
-            {
-                mergeWithChild = false;
-                break;
-            }
+            return;
         }
-        if (mergeWithChild)
+        while (true)
         {
+            bool didMerge = false;
             Node::ChildMap merged;
-            for (const Node::ChildMap::value_type& kv : node->children)
+            for (const Node::ChildMap::value_type& kv : node.children)
             {
-                Node* child = &nodes[kv.second];
-                for (const Node::ChildMap::value_type& childKv :
-                     child->children)
+                Node& child = nodes[kv.second];
+                if (child.isSimpleNode())
+                {
+                    for (const Node::ChildMap::value_type& childKv :
+                         child.children)
+                    {
+                        merged[kv.first + childKv.first] = childKv.second;
+                        didMerge = true;
+                    }
+                }
+                else
                 {
-                    merged[kv.first + childKv.first] = childKv.second;
+                    merged[kv.first] = kv.second;
                 }
             }
-            node->children = std::move(merged);
-            optimizeNode(node);
-        }
-        else
-        {
-            for (const Node::ChildMap::value_type& kv : node->children)
+            node.children = std::move(merged);
+            if (!didMerge)
             {
-                Node* child = &nodes[kv.second];
-                optimizeNode(child);
+                break;
             }
         }
+
+        for (const Node::ChildMap::value_type& kv : node.children)
+        {
+            optimizeNode(nodes[kv.second]);
+        }
     }
 
     void optimize()
@@ -124,74 +122,57 @@ class Trie
         optimize();
     }
 
-    void findRouteIndexes(const std::string& reqUrl,
-                          std::vector<unsigned>& routeIndexes,
-                          const Node* node = nullptr, unsigned pos = 0) const
+    void findRouteIndexesHelper(std::string_view reqUrl,
+                                std::vector<unsigned>& routeIndexes,
+                                const Node& node) const
     {
-        if (node == nullptr)
-        {
-            node = head();
-        }
-        for (const Node::ChildMap::value_type& kv : node->children)
+        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())
+            const Node& child = nodes[kv.second];
+            if (reqUrl.empty())
             {
-                if (child->ruleIndex != 0 && fragment != "/")
+                if (child.ruleIndex != 0 && fragment != "/")
                 {
-                    routeIndexes.push_back(child->ruleIndex);
+                    routeIndexes.push_back(child.ruleIndex);
                 }
-                findRouteIndexes(reqUrl, routeIndexes, child,
-                                 static_cast<unsigned>(pos + fragment.size()));
+                findRouteIndexesHelper(reqUrl, routeIndexes, child);
             }
             else
             {
-                if (reqUrl.compare(pos, fragment.size(), fragment) == 0)
+                if (reqUrl.starts_with(fragment))
                 {
-                    findRouteIndexes(
-                        reqUrl, routeIndexes, child,
-                        static_cast<unsigned>(pos + fragment.size()));
+                    findRouteIndexesHelper(reqUrl.substr(fragment.size()),
+                                           routeIndexes, child);
                 }
             }
         }
     }
 
-    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
+    void findRouteIndexes(const std::string& reqUrl,
+                          std::vector<unsigned>& routeIndexes) const
     {
-        std::vector<std::string> empty;
-        if (params == nullptr)
-        {
-            params = &empty;
-        }
+        findRouteIndexesHelper(reqUrl, routeIndexes, head());
+    }
 
-        unsigned found{};
-        std::vector<std::string> matchParams;
+    struct FindResult
+    {
+        unsigned ruleIndex;
+        std::vector<std::string> params;
+    };
 
-        if (node == nullptr)
-        {
-            node = head();
-        }
-        if (pos == reqUrl.size())
+  private:
+    FindResult findHelper(const std::string_view reqUrl, const Node& node,
+                          std::vector<std::string>& params) const
+    {
+        if (reqUrl.empty())
         {
-            return {node->ruleIndex, *params};
+            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)
+        if (node.stringParamChild != 0U)
         {
-            size_t epos = pos;
+            size_t epos = 0;
             for (; epos < reqUrl.size(); epos++)
             {
                 if (reqUrl[epos] == '/')
@@ -200,137 +181,132 @@ class Trie
                 }
             }
 
-            if (epos != pos)
+            if (epos != 0)
             {
-                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();
+                params.emplace_back(reqUrl.substr(0, epos));
+                FindResult ret = findHelper(
+                    reqUrl.substr(epos), nodes[node.stringParamChild], params);
+                if (ret.ruleIndex != 0U)
+                {
+                    return {ret.ruleIndex, std::move(ret.params)};
+                }
+                params.pop_back();
             }
         }
 
-        if (node->paramChildrens[static_cast<size_t>(ParamType::PATH)] != 0U)
+        if (node.pathParamChild != 0U)
         {
-            size_t epos = reqUrl.size();
-
-            if (epos != pos)
+            params.emplace_back(reqUrl);
+            FindResult ret = findHelper("", nodes[node.pathParamChild], params);
+            if (ret.ruleIndex != 0U)
             {
-                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();
+                return {ret.ruleIndex, std::move(ret.params)};
             }
+            params.pop_back();
         }
 
-        for (const Node::ChildMap::value_type& kv : node->children)
+        for (const Node::ChildMap::value_type& kv : node.children)
         {
             const std::string& fragment = kv.first;
-            const Node* child = &nodes[kv.second];
+            const Node& child = nodes[kv.second];
 
-            if (reqUrl.compare(pos, fragment.size(), fragment) == 0)
+            if (reqUrl.starts_with(fragment))
             {
-                std::pair<unsigned, std::vector<std::string>> ret =
-                    find(reqUrl, child, pos + fragment.size(), params);
-                updateFound(ret);
+                FindResult ret = findHelper(reqUrl.substr(fragment.size()),
+                                            child, params);
+                if (ret.ruleIndex != 0U)
+                {
+                    return {ret.ruleIndex, std::move(ret.params)};
+                }
             }
         }
 
-        return {found, matchParams};
+        return {0U, std::vector<std::string>()};
+    }
+
+  public:
+    FindResult find(const std::string_view reqUrl) const
+    {
+        std::vector<std::string> start;
+        return findHelper(reqUrl, head(), start);
     }
 
-    void add(const std::string& url, unsigned ruleIndex)
+    void add(std::string_view url, unsigned ruleIndex)
     {
         size_t idx = 0;
 
-        for (unsigned i = 0; i < url.size(); i++)
+        while (!url.empty())
         {
-            char c = url[i];
+            char c = url[0];
             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)
+                bool found = false;
+                for (const std::string_view str1 :
+                     {"<str>", "<string>", "<path>"})
                 {
-                    if (url.compare(i, x.second.size(), x.second) == 0)
+                    if (!url.starts_with(str1))
+                    {
+                        continue;
+                    }
+                    found = true;
+                    Node& node = nodes[idx];
+                    size_t* param = &node.stringParamChild;
+                    if (str1 == "<path>")
                     {
-                        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;
+                        param = &node.pathParamChild;
                     }
+                    if (*param == 0U)
+                    {
+                        *param = newNode();
+                    }
+                    idx = *param;
+
+                    url.remove_prefix(str1.size());
+                    break;
+                }
+                if (found)
+                {
+                    continue;
                 }
 
-                i--;
+                BMCWEB_LOG_CRITICAL("Cant find tag for {}", url);
+                return;
             }
-            else
+            std::string piece(&c, 1);
+            if (!nodes[idx].children.contains(piece))
             {
-                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];
+                unsigned newNodeIdx = newNode();
+                nodes[idx].children.emplace(piece, newNodeIdx);
             }
+            idx = nodes[idx].children[piece];
+            url.remove_prefix(1);
         }
         if (nodes[idx].ruleIndex != 0U)
         {
-            throw std::runtime_error("handler already exists for " + url);
+            throw std::runtime_error(
+                std::format("handler already exists for {}", url));
         }
         nodes[idx].ruleIndex = ruleIndex;
     }
 
   private:
-    void debugNodePrint(Node* n, size_t level)
+    void debugNodePrint(Node& n, size_t level)
     {
-        std::string indent(2U * level, ' ');
-        for (size_t i = 0; i < static_cast<size_t>(ParamType::MAX); i++)
+        std::string spaces(level, ' ');
+        if (n.stringParamChild != 0U)
         {
-            if (n->paramChildrens[i] != 0U)
-            {
-                switch (static_cast<ParamType>(i))
-                {
-                    case ParamType::STRING:
-                        BMCWEB_LOG_DEBUG("{}({}) <str>", indent,
-                                         n->paramChildrens[i]);
-                        break;
-                    case ParamType::PATH:
-                        BMCWEB_LOG_DEBUG("{}({}) <path>", indent,
-                                         n->paramChildrens[i]);
-                        BMCWEB_LOG_DEBUG("<path>");
-                        break;
-                    default:
-                        BMCWEB_LOG_DEBUG("{}<ERROR>", indent);
-                        break;
-                }
-
-                debugNodePrint(&nodes[n->paramChildrens[i]], level + 1);
-            }
+            BMCWEB_LOG_DEBUG("{}<str>", spaces);
+            debugNodePrint(nodes[n.stringParamChild], level + 5);
+        }
+        if (n.pathParamChild != 0U)
+        {
+            BMCWEB_LOG_DEBUG("{} <path>", spaces);
+            debugNodePrint(nodes[n.pathParamChild], level + 6);
         }
-        for (const Node::ChildMap::value_type& kv : n->children)
+        for (const Node::ChildMap::value_type& kv : n.children)
         {
-            BMCWEB_LOG_DEBUG("{}({}{}) ", indent, kv.second, kv.first);
-            debugNodePrint(&nodes[kv.second], level + 1);
+            BMCWEB_LOG_DEBUG("{}{}", spaces, kv.first);
+            debugNodePrint(nodes[kv.second], level + kv.first.size());
         }
     }
 
@@ -341,14 +317,14 @@ class Trie
     }
 
   private:
-    const Node* head() const
+    const Node& head() const
     {
-        return &nodes.front();
+        return nodes.front();
     }
 
-    Node* head()
+    Node& head()
     {
-        return &nodes.front();
+        return nodes.front();
     }
 
     unsigned newNode()
@@ -375,11 +351,10 @@ class Router
         return *ptr;
     }
 
-    template <uint64_t N>
+    template <uint64_t NumArgs>
     auto& newRuleTagged(const std::string& rule)
     {
-        constexpr size_t numArgs = utility::numArgsFromTag(N);
-        if constexpr (numArgs == 0)
+        if constexpr (NumArgs == 0)
         {
             using RuleT = TaggedRule<>;
             std::unique_ptr<RuleT> ruleObject = std::make_unique<RuleT>(rule);
@@ -387,7 +362,7 @@ class Router
             allRules.emplace_back(std::move(ruleObject));
             return *ptr;
         }
-        else if constexpr (numArgs == 1)
+        else if constexpr (NumArgs == 1)
         {
             using RuleT = TaggedRule<std::string>;
             std::unique_ptr<RuleT> ruleObject = std::make_unique<RuleT>(rule);
@@ -395,7 +370,7 @@ class Router
             allRules.emplace_back(std::move(ruleObject));
             return *ptr;
         }
-        else if constexpr (numArgs == 2)
+        else if constexpr (NumArgs == 2)
         {
             using RuleT = TaggedRule<std::string, std::string>;
             std::unique_ptr<RuleT> ruleObject = std::make_unique<RuleT>(rule);
@@ -403,7 +378,7 @@ class Router
             allRules.emplace_back(std::move(ruleObject));
             return *ptr;
         }
-        else if constexpr (numArgs == 3)
+        else if constexpr (NumArgs == 3)
         {
             using RuleT = TaggedRule<std::string, std::string, std::string>;
             std::unique_ptr<RuleT> ruleObject = std::make_unique<RuleT>(rule);
@@ -411,7 +386,7 @@ class Router
             allRules.emplace_back(std::move(ruleObject));
             return *ptr;
         }
-        else if constexpr (numArgs == 4)
+        else if constexpr (NumArgs == 4)
         {
             using RuleT =
                 TaggedRule<std::string, std::string, std::string, std::string>;
@@ -429,7 +404,7 @@ class Router
             allRules.emplace_back(std::move(ruleObject));
             return *ptr;
         }
-        static_assert(numArgs <= 5, "Max number of args supported is 5");
+        static_assert(NumArgs <= 5, "Max number of args supported is 5");
     }
 
     void internalAddRuleObject(const std::string& rule, BaseRule* ruleObject)
@@ -502,17 +477,16 @@ class Router
             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())
+        Trie::FindResult found = perMethod.trie.find(url);
+        if (found.ruleIndex >= perMethod.rules.size())
         {
             throw std::runtime_error("Trie internal structure corrupted!");
         }
         // Found a 404 route, switch that in
-        if (found.first != 0U)
+        if (found.ruleIndex != 0U)
         {
-            route.rule = perMethod.rules[found.first];
-            route.params = std::move(found.second);
+            route.rule = perMethod.rules[found.ruleIndex];
+            route.params = std::move(found.params);
         }
         return route;
     }
@@ -569,9 +543,8 @@ class Router
         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;
+        Trie::FindResult found = trie.find(req.url().encoded_path());
+        unsigned ruleIndex = found.ruleIndex;
         if (ruleIndex == 0U)
         {
             BMCWEB_LOG_DEBUG("Cannot match rules {}", req.url().encoded_path());
@@ -682,9 +655,7 @@ class Router
     {
         for (size_t i = 0; i < perMethods.size(); i++)
         {
-            BMCWEB_LOG_DEBUG("{}",
-                             boost::beast::http::to_string(
-                                 static_cast<boost::beast::http::verb>(i)));
+            BMCWEB_LOG_DEBUG("{}", httpVerbToString(static_cast<HttpVerb>(i)));
             perMethods[i].trie.debugPrint();
         }
     }
diff --git a/http/utility.hpp b/http/utility.hpp
index 0476d73c74..7633c395af 100644
--- a/http/utility.hpp
+++ b/http/utility.hpp
@@ -31,28 +31,11 @@ namespace crow
 namespace utility
 {
 
-enum class TypeCode : uint8_t
-{
-    Unspecified = 0,
-    String = 1,
-    Path = 2,
-    Max = 3,
-};
-
-// Remove when we have c++23
-template <typename E>
-constexpr typename std::underlying_type<E>::type toUnderlying(E e) noexcept
-{
-    return static_cast<typename std::underlying_type<E>::type>(e);
-}
-
 constexpr uint64_t getParameterTag(std::string_view url)
 {
     uint64_t tagValue = 0;
     size_t urlSegmentIndex = std::string_view::npos;
 
-    size_t paramIndex = 0;
-
     for (size_t urlIndex = 0; urlIndex < url.size(); urlIndex++)
     {
         char character = url[urlIndex];
@@ -73,25 +56,14 @@ constexpr uint64_t getParameterTag(std::string_view url)
             std::string_view tag = url.substr(urlSegmentIndex,
                                               urlIndex + 1 - urlSegmentIndex);
 
-            // Note, this is a really lame way to do std::pow(6, paramIndex)
-            // std::pow doesn't work in constexpr in clang.
-            // Ideally in the future we'd move this to use a power of 2 packing
-            // (probably 8 instead of 6) so that these just become bit shifts
-            uint64_t insertIndex = 1;
-            for (size_t unused = 0; unused < paramIndex; unused++)
-            {
-                insertIndex *= 3;
-            }
-
             if (tag == "<str>" || tag == "<string>")
             {
-                tagValue += insertIndex * toUnderlying(TypeCode::String);
+                tagValue++;
             }
             if (tag == "<path>")
             {
-                tagValue += insertIndex * toUnderlying(TypeCode::Path);
+                tagValue++;
             }
-            paramIndex++;
             urlSegmentIndex = std::string_view::npos;
         }
     }
@@ -102,18 +74,6 @@ constexpr uint64_t getParameterTag(std::string_view url)
     return tagValue;
 }
 
-constexpr size_t numArgsFromTag(int tag)
-{
-    size_t ret = 0;
-    while (tag > 0)
-    {
-        // Move to the next tag by removing the bottom bits from the number
-        tag /= toUnderlying(TypeCode::Max);
-        ret++;
-    }
-    return ret;
-};
-
 class Base64Encoder
 {
     char overflow1 = '\0';