xref: /openbmc/bmcweb/http/routing/trie.hpp (revision c1a75ebc267a78853fb26a3da8c6b3388e6ee07c)
1 // SPDX-License-Identifier: Apache-2.0
2 // SPDX-FileCopyrightText: Copyright OpenBMC Authors
3 
4 #pragma once
5 
6 #include "logging.hpp"
7 
8 #include <boost/container/flat_map.hpp>
9 #include <boost/container/small_vector.hpp>
10 
11 #include <cstddef>
12 #include <format>
13 #include <functional>
14 #include <stdexcept>
15 #include <string>
16 #include <string_view>
17 #include <utility>
18 #include <vector>
19 
20 namespace crow
21 {
22 
23 struct Node
24 {
25     unsigned ruleIndex = 0U;
26 
27     size_t stringParamChild = 0U;
28     size_t pathParamChild = 0U;
29 
30     using ChildMap = boost::container::flat_map<
31         std::string, unsigned, std::less<>,
32         boost::container::small_vector<std::pair<std::string, unsigned>, 1>>;
33     ChildMap children;
34 
isSimpleNodecrow::Node35     bool isSimpleNode() const
36     {
37         return ruleIndex == 0 && stringParamChild == 0 && pathParamChild == 0;
38     }
39 };
40 template <typename ContainedType>
41 class Trie
42 {
43   public:
Trie()44     Trie() : nodes(1) {}
45 
46   private:
optimizeNode(ContainedType & node)47     void optimizeNode(ContainedType& node)
48     {
49         if (node.stringParamChild != 0U)
50         {
51             optimizeNode(nodes[node.stringParamChild]);
52         }
53         if (node.pathParamChild != 0U)
54         {
55             optimizeNode(nodes[node.pathParamChild]);
56         }
57 
58         if (node.children.empty())
59         {
60             return;
61         }
62         while (true)
63         {
64             bool didMerge = false;
65             typename ContainedType::ChildMap merged;
66             for (const typename ContainedType::ChildMap::value_type& kv :
67                  node.children)
68             {
69                 ContainedType& child = nodes[kv.second];
70                 if (child.isSimpleNode())
71                 {
72                     for (const typename ContainedType::ChildMap::value_type&
73                              childKv : child.children)
74                     {
75                         merged[kv.first + childKv.first] = childKv.second;
76                         didMerge = true;
77                     }
78                 }
79                 else
80                 {
81                     merged[kv.first] = kv.second;
82                 }
83             }
84             node.children = std::move(merged);
85             if (!didMerge)
86             {
87                 break;
88             }
89         }
90 
91         for (const typename ContainedType::ChildMap::value_type& kv :
92              node.children)
93         {
94             optimizeNode(nodes[kv.second]);
95         }
96     }
97 
optimize()98     void optimize()
99     {
100         optimizeNode(head());
101     }
102 
103   public:
validate()104     void validate()
105     {
106         optimize();
107     }
108 
findRouteIndexesHelper(std::string_view reqUrl,std::vector<unsigned> & routeIndexes,const ContainedType & node) const109     void findRouteIndexesHelper(std::string_view reqUrl,
110                                 std::vector<unsigned>& routeIndexes,
111                                 const ContainedType& node) const
112     {
113         for (const typename ContainedType::ChildMap::value_type& kv :
114              node.children)
115         {
116             const std::string& fragment = kv.first;
117             const ContainedType& child = nodes[kv.second];
118             if (reqUrl.empty())
119             {
120                 if (child.ruleIndex != 0 && fragment != "/")
121                 {
122                     routeIndexes.push_back(child.ruleIndex);
123                 }
124                 findRouteIndexesHelper(reqUrl, routeIndexes, child);
125             }
126             else
127             {
128                 if (reqUrl.starts_with(fragment))
129                 {
130                     findRouteIndexesHelper(reqUrl.substr(fragment.size()),
131                                            routeIndexes, child);
132                 }
133             }
134         }
135     }
136 
findRouteIndexes(const std::string & reqUrl,std::vector<unsigned> & routeIndexes) const137     void findRouteIndexes(const std::string& reqUrl,
138                           std::vector<unsigned>& routeIndexes) const
139     {
140         findRouteIndexesHelper(reqUrl, routeIndexes, head());
141     }
142 
143     struct FindResult
144     {
145         unsigned ruleIndex = 0;
146         std::vector<std::string> params;
147     };
148 
149   private:
findHelper(const std::string_view reqUrl,const ContainedType & node,std::vector<std::string> & params) const150     FindResult findHelper(const std::string_view reqUrl,
151                           const ContainedType& node,
152                           std::vector<std::string>& params) const
153     {
154         if (reqUrl.empty())
155         {
156             return {node.ruleIndex, params};
157         }
158 
159         if (node.stringParamChild != 0U)
160         {
161             size_t epos = 0;
162             for (; epos < reqUrl.size(); epos++)
163             {
164                 if (reqUrl[epos] == '/')
165                 {
166                     break;
167                 }
168             }
169 
170             if (epos != 0)
171             {
172                 params.emplace_back(reqUrl.substr(0, epos));
173                 FindResult ret = findHelper(
174                     reqUrl.substr(epos), nodes[node.stringParamChild], params);
175                 if (ret.ruleIndex != 0U)
176                 {
177                     return {ret.ruleIndex, std::move(ret.params)};
178                 }
179                 params.pop_back();
180             }
181         }
182 
183         if (node.pathParamChild != 0U)
184         {
185             params.emplace_back(reqUrl);
186             FindResult ret = findHelper("", nodes[node.pathParamChild], params);
187             if (ret.ruleIndex != 0U)
188             {
189                 return {ret.ruleIndex, std::move(ret.params)};
190             }
191             params.pop_back();
192         }
193 
194         for (const typename ContainedType::ChildMap::value_type& kv :
195              node.children)
196         {
197             const std::string& fragment = kv.first;
198             const ContainedType& child = nodes[kv.second];
199 
200             if (reqUrl.starts_with(fragment))
201             {
202                 FindResult ret =
203                     findHelper(reqUrl.substr(fragment.size()), child, params);
204                 if (ret.ruleIndex != 0U)
205                 {
206                     return {ret.ruleIndex, std::move(ret.params)};
207                 }
208             }
209         }
210 
211         return {0U, std::vector<std::string>()};
212     }
213 
214   public:
find(const std::string_view reqUrl) const215     FindResult find(const std::string_view reqUrl) const
216     {
217         std::vector<std::string> start;
218         return findHelper(reqUrl, head(), start);
219     }
220 
add(std::string_view urlIn,unsigned ruleIndex)221     void add(std::string_view urlIn, unsigned ruleIndex)
222     {
223         size_t idx = 0;
224 
225         std::string_view url = urlIn;
226 
227         while (!url.empty())
228         {
229             char c = url[0];
230             if (c == '<')
231             {
232                 bool found = false;
233                 for (const std::string_view str1 :
234                      {"<str>", "<string>", "<path>"})
235                 {
236                     if (!url.starts_with(str1))
237                     {
238                         continue;
239                     }
240                     found = true;
241                     ContainedType& node = nodes[idx];
242                     size_t* param = &node.stringParamChild;
243                     if (str1 == "<path>")
244                     {
245                         param = &node.pathParamChild;
246                     }
247                     if (*param == 0U)
248                     {
249                         *param = newNode();
250                     }
251                     idx = *param;
252 
253                     url.remove_prefix(str1.size());
254                     break;
255                 }
256                 if (found)
257                 {
258                     continue;
259                 }
260 
261                 BMCWEB_LOG_CRITICAL("Can't find tag for {}", urlIn);
262                 return;
263             }
264             std::string piece(&c, 1);
265             if (!nodes[idx].children.contains(piece))
266             {
267                 unsigned newNodeIdx = newNode();
268                 nodes[idx].children.emplace(piece, newNodeIdx);
269             }
270             idx = nodes[idx].children[piece];
271             url.remove_prefix(1);
272         }
273         ContainedType& node = nodes[idx];
274         if (node.ruleIndex != 0U)
275         {
276             BMCWEB_LOG_CRITICAL("handler already exists for \"{}\"", urlIn);
277             throw std::runtime_error(
278                 std::format("handler already exists for \"{}\"", urlIn));
279         }
280         node.ruleIndex = ruleIndex;
281     }
282 
283   private:
debugNodePrint(ContainedType & n,size_t level)284     void debugNodePrint(ContainedType& n, size_t level)
285     {
286         std::string spaces(level, ' ');
287         if (n.stringParamChild != 0U)
288         {
289             BMCWEB_LOG_DEBUG("{}<str>", spaces);
290             debugNodePrint(nodes[n.stringParamChild], level + 5);
291         }
292         if (n.pathParamChild != 0U)
293         {
294             BMCWEB_LOG_DEBUG("{} <path>", spaces);
295             debugNodePrint(nodes[n.pathParamChild], level + 6);
296         }
297         for (const typename ContainedType::ChildMap::value_type& kv :
298              n.children)
299         {
300             BMCWEB_LOG_DEBUG("{}{}", spaces, kv.first);
301             debugNodePrint(nodes[kv.second], level + kv.first.size());
302         }
303     }
304 
305   public:
debugPrint()306     void debugPrint()
307     {
308         debugNodePrint(head(), 0U);
309     }
310 
311   protected:
head() const312     const ContainedType& head() const
313     {
314         return nodes.front();
315     }
316 
head()317     ContainedType& head()
318     {
319         return nodes.front();
320     }
321 
newNode()322     unsigned newNode()
323     {
324         nodes.resize(nodes.size() + 1);
325         return static_cast<unsigned>(nodes.size() - 1);
326     }
327 
328     std::vector<ContainedType> nodes{};
329 };
330 } // namespace crow
331