xref: /openbmc/bmcweb/http/routing/trie.hpp (revision a9da2b2b50758ec9657ab7034e57dadb3e62abd0) 
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                     if (str1 == "<path>")
242                     {
243                         if (nodes[idx].pathParamChild == 0U)
244                         {
245                             unsigned newNodeIdx = newNode();
246                             nodes[idx].pathParamChild = newNodeIdx;
247                         }
248                         idx = nodes[idx].pathParamChild;
249                     }
250                     else
251                     {
252                         if (nodes[idx].stringParamChild == 0U)
253                         {
254                             unsigned newNodeIdx = newNode();
255                             nodes[idx].stringParamChild = newNodeIdx;
256                         }
257                         idx = nodes[idx].stringParamChild;
258                     }
259 
260                     url.remove_prefix(str1.size());
261                     break;
262                 }
263                 if (found)
264                 {
265                     continue;
266                 }
267 
268                 BMCWEB_LOG_CRITICAL("Can't find tag for {}", urlIn);
269                 return;
270             }
271             std::string piece(&c, 1);
272             if (!nodes[idx].children.contains(piece))
273             {
274                 unsigned newNodeIdx = newNode();
275                 nodes[idx].children.emplace(piece, newNodeIdx);
276             }
277             idx = nodes[idx].children[piece];
278             url.remove_prefix(1);
279         }
280         ContainedType& node = nodes[idx];
281         if (node.ruleIndex != 0U)
282         {
283             BMCWEB_LOG_CRITICAL("handler already exists for \"{}\"", urlIn);
284             throw std::runtime_error(
285                 std::format("handler already exists for \"{}\"", urlIn));
286         }
287         node.ruleIndex = ruleIndex;
288     }
289 
290   private:
debugNodePrint(ContainedType & n,size_t level)291     void debugNodePrint(ContainedType& n, size_t level)
292     {
293         std::string spaces(level, ' ');
294         if (n.stringParamChild != 0U)
295         {
296             BMCWEB_LOG_DEBUG("{}<str>", spaces);
297             debugNodePrint(nodes[n.stringParamChild], level + 5);
298         }
299         if (n.pathParamChild != 0U)
300         {
301             BMCWEB_LOG_DEBUG("{} <path>", spaces);
302             debugNodePrint(nodes[n.pathParamChild], level + 6);
303         }
304         for (const typename ContainedType::ChildMap::value_type& kv :
305              n.children)
306         {
307             BMCWEB_LOG_DEBUG("{}{}", spaces, kv.first);
308             debugNodePrint(nodes[kv.second], level + kv.first.size());
309         }
310     }
311 
312   public:
debugPrint()313     void debugPrint()
314     {
315         debugNodePrint(head(), 0U);
316     }
317 
318   protected:
head() const319     const ContainedType& head() const
320     {
321         return nodes.front();
322     }
323 
head()324     ContainedType& head()
325     {
326         return nodes.front();
327     }
328 
newNode()329     unsigned newNode()
330     {
331         nodes.resize(nodes.size() + 1);
332         return static_cast<unsigned>(nodes.size() - 1);
333     }
334 
335     std::vector<ContainedType> nodes{};
336 };
337 } // namespace crow
338