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