720 uint16_t rule_index{};
722 uint16_t blueprint_index{INVALID_BP_ID};
724 ParamType param = ParamType::MAX;
725 std::vector<Node> children;
727 bool IsSimpleNode()
const
729 return !rule_index &&
730 blueprint_index == INVALID_BP_ID &&
731 children.size() < 2 &&
732 param == ParamType::MAX &&
733 std::all_of(std::begin(children), std::end(children), [](
const Node& x) {
734 return x.param == ParamType::MAX;
738 Node& add_child_node()
740 children.emplace_back();
741 return children.back();
752 return head_.children.empty();
757 for (
auto& child : head_.children)
765 void optimizeNode(Node& node)
767 if (node.children.empty())
769 if (node.IsSimpleNode())
771 auto children_temp = std::move(node.children);
772 auto& child_temp = children_temp[0];
773 node.key += child_temp.key;
774 node.rule_index = child_temp.rule_index;
775 node.blueprint_index = child_temp.blueprint_index;
776 node.children = std::move(child_temp.children);
781 for (
auto& child : node.children)
788 void debug_node_print(
const Node& node,
int level)
790 if (node.param != ParamType::MAX)
795 CROW_LOG_DEBUG << std::string(3 * level,
' ') <<
"└➝ "
798 case ParamType::UINT:
799 CROW_LOG_DEBUG << std::string(3 * level,
' ') <<
"└➝ "
802 case ParamType::DOUBLE:
803 CROW_LOG_DEBUG << std::string(3 * level,
' ') <<
"└➝ "
806 case ParamType::STRING:
807 CROW_LOG_DEBUG << std::string(3 * level,
' ') <<
"└➝ "
810 case ParamType::PATH:
811 CROW_LOG_DEBUG << std::string(3 * level,
' ') <<
"└➝ "
815 CROW_LOG_DEBUG << std::string(3 * level,
' ') <<
"└➝ "
821 CROW_LOG_DEBUG << std::string(3 * level,
' ') <<
"└➝ " << node.key;
823 for (
const auto& child : node.children)
825 debug_node_print(child, level + 1);
832 CROW_LOG_DEBUG <<
"└➙ ROOT";
833 for (
const auto& child : head_.children)
834 debug_node_print(child, 1);
839 if (!head_.IsSimpleNode())
840 throw std::runtime_error(
"Internal error: Trie header should be simple!");
845 routing_handle_result find(
const std::string& req_url,
const Node& node,
unsigned pos = 0, routing_params* params =
nullptr, std::vector<uint16_t>* blueprints =
nullptr)
const
848 routing_params empty;
849 if (params ==
nullptr)
852 std::vector<uint16_t> MT;
853 if (blueprints ==
nullptr)
857 std::vector<uint16_t> found_BP;
858 routing_params match_params;
860 auto update_found = [&found, &found_BP, &match_params](routing_handle_result& ret) {
861 found_BP = std::move(ret.blueprint_indices);
862 if (ret.rule_index && (!found || found > ret.rule_index))
864 found = ret.rule_index;
865 match_params = std::move(ret.r_params);
870 if (pos == req_url.size())
872 found_BP = std::move(*blueprints);
873 return routing_handle_result{node.rule_index, *blueprints, *params};
876 bool found_fragment =
false;
878 for (
const auto& child : node.children)
880 if (child.param != ParamType::MAX)
882 if (child.param == ParamType::INT)
884 char c = req_url[pos];
885 if ((c >=
'0' && c <=
'9') || c ==
'+' || c ==
'-')
889 long long int value = strtoll(req_url.data() + pos, &eptr, 10);
890 if (errno != ERANGE && eptr != req_url.data() + pos)
892 found_fragment =
true;
893 params->int_params.push_back(value);
894 if (child.blueprint_index != INVALID_BP_ID) blueprints->push_back(child.blueprint_index);
895 auto ret = find(req_url, child, eptr - req_url.data(), params, blueprints);
897 params->int_params.pop_back();
898 if (!blueprints->empty()) blueprints->pop_back();
903 else if (child.param == ParamType::UINT)
905 char c = req_url[pos];
906 if ((c >=
'0' && c <=
'9') || c ==
'+')
910 unsigned long long int value = strtoull(req_url.data() + pos, &eptr, 10);
911 if (errno != ERANGE && eptr != req_url.data() + pos)
913 found_fragment =
true;
914 params->uint_params.push_back(value);
915 if (child.blueprint_index != INVALID_BP_ID) blueprints->push_back(child.blueprint_index);
916 auto ret = find(req_url, child, eptr - req_url.data(), params, blueprints);
918 params->uint_params.pop_back();
919 if (!blueprints->empty()) blueprints->pop_back();
924 else if (child.param == ParamType::DOUBLE)
926 char c = req_url[pos];
927 if ((c >=
'0' && c <=
'9') || c ==
'+' || c ==
'-' || c ==
'.')
931 double value = strtod(req_url.data() + pos, &eptr);
932 if (errno != ERANGE && eptr != req_url.data() + pos)
934 found_fragment =
true;
935 params->double_params.push_back(value);
936 if (child.blueprint_index != INVALID_BP_ID) blueprints->push_back(child.blueprint_index);
937 auto ret = find(req_url, child, eptr - req_url.data(), params, blueprints);
939 params->double_params.pop_back();
940 if (!blueprints->empty()) blueprints->pop_back();
945 else if (child.param == ParamType::STRING)
948 for (; epos < req_url.size(); epos++)
950 if (req_url[epos] ==
'/')
956 found_fragment =
true;
957 params->string_params.push_back(req_url.substr(pos, epos - pos));
958 if (child.blueprint_index != INVALID_BP_ID) blueprints->push_back(child.blueprint_index);
959 auto ret = find(req_url, child, epos, params, blueprints);
961 params->string_params.pop_back();
962 if (!blueprints->empty()) blueprints->pop_back();
966 else if (child.param == ParamType::PATH)
968 size_t epos = req_url.size();
972 found_fragment =
true;
973 params->string_params.push_back(req_url.substr(pos, epos - pos));
974 if (child.blueprint_index != INVALID_BP_ID) blueprints->push_back(child.blueprint_index);
975 auto ret = find(req_url, child, epos, params, blueprints);
977 params->string_params.pop_back();
978 if (!blueprints->empty()) blueprints->pop_back();
985 const std::string& fragment = child.key;
986 if (req_url.compare(pos, fragment.size(), fragment) == 0)
988 found_fragment =
true;
989 if (child.blueprint_index != INVALID_BP_ID) blueprints->push_back(child.blueprint_index);
990 auto ret = find(req_url, child, pos + fragment.size(), params, blueprints);
992 if (!blueprints->empty()) blueprints->pop_back();
998 found_BP = std::move(*blueprints);
1000 return routing_handle_result{found, found_BP, match_params};
1003 routing_handle_result find(
const std::string& req_url)
const
1005 return find(req_url, head_);
1009 void add(
const std::string& url, uint16_t rule_index,
unsigned bp_prefix_length = 0, uint16_t blueprint_index = INVALID_BP_ID)
1013 bool has_blueprint = bp_prefix_length != 0 && blueprint_index != INVALID_BP_ID;
1015 for (
unsigned i = 0; i < url.size(); i++)
1020 static struct ParamTraits
1026 {ParamType::INT,
"<int>"},
1027 {ParamType::UINT,
"<uint>"},
1028 {ParamType::DOUBLE,
"<float>"},
1029 {ParamType::DOUBLE,
"<double>"},
1030 {ParamType::STRING,
"<str>"},
1031 {ParamType::STRING,
"<string>"},
1032 {ParamType::PATH,
"<path>"},
1035 for (
const auto& x : paramTraits)
1037 if (url.compare(i, x.name.size(), x.name) == 0)
1040 for (
auto& child : idx->children)
1042 if (child.param == x.type)
1053 auto new_node_idx = &idx->add_child_node();
1054 new_node_idx->param = x.type;
1066 bool piece_found =
false;
1067 for (
auto& child : idx->children)
1069 if (child.key[0] == c)
1078 auto new_node_idx = &idx->add_child_node();
1079 new_node_idx->key = c;
1081 if (has_blueprint && i == bp_prefix_length)
1082 new_node_idx->blueprint_index = blueprint_index;
1089 if (idx->rule_index)
1090 throw std::runtime_error(
"handler already exists for " + url);
1091 idx->rule_index = rule_index;
1259 DynamicRule& new_rule_dynamic(
const std::string& rule)
1262 all_rules_.emplace_back(ruleObject);
1267 template<u
int64_t N>
1268 typename black_magic::arguments<N>::type::template rebind<TaggedRule>& new_rule_tagged(
const std::string& rule)
1270 using RuleT =
typename black_magic::arguments<N>::type::template rebind<TaggedRule>;
1272 auto ruleObject =
new RuleT(rule);
1273 all_rules_.emplace_back(ruleObject);
1280 return catchall_rule_;
1283 void internal_add_rule_object(
const std::string& rule,
BaseRule* ruleObject)
1285 internal_add_rule_object(rule, ruleObject, INVALID_BP_ID, blueprints_);
1288 void internal_add_rule_object(
const std::string& rule,
BaseRule* ruleObject,
const uint16_t& BP_index, std::vector<Blueprint*>& blueprints)
1290 bool has_trailing_slash =
false;
1291 std::string rule_without_trailing_slash;
1292 if (rule.size() > 1 && rule.back() ==
'/')
1294 has_trailing_slash =
true;
1295 rule_without_trailing_slash = rule;
1296 rule_without_trailing_slash.pop_back();
1299 ruleObject->mw_indices_.pack();
1301 ruleObject->foreach_method([&](
int method) {
1302 per_methods_[method].rules.emplace_back(ruleObject);
1303 per_methods_[method].trie.add(rule, per_methods_[method].rules.size() - 1, BP_index != INVALID_BP_ID ? blueprints[BP_index]->prefix().length() : 0, BP_index);
1307 if (has_trailing_slash)
1309 per_methods_[method].trie.add(rule_without_trailing_slash, RULE_SPECIAL_REDIRECT_SLASH, BP_index != INVALID_BP_ID ? blueprints[BP_index]->prefix().length() : 0, BP_index);
1313 ruleObject->set_added();
1316 void register_blueprint(
Blueprint& blueprint)
1318 if (std::find(blueprints_.begin(), blueprints_.end(), &blueprint) == blueprints_.end())
1320 blueprints_.emplace_back(&blueprint);
1323 throw std::runtime_error(
"blueprint \"" + blueprint.prefix_ +
"\" already exists in router");
1326 void get_recursive_child_methods(
Blueprint* blueprint, std::vector<HTTPMethod>& methods)
1329 if (blueprint->static_dir_.empty() && blueprint->all_rules_.empty())
1331 for (
Blueprint* bp : blueprint->blueprints_)
1333 get_recursive_child_methods(bp, methods);
1336 else if (!blueprint->static_dir_.empty())
1337 methods.emplace_back(HTTPMethod::Get);
1338 for (
auto& rule : blueprint->all_rules_)
1340 rule->foreach_method([&methods](
unsigned method) {
1341 HTTPMethod method_final =
static_cast<HTTPMethod
>(method);
1342 if (std::find(methods.begin(), methods.end(), method_final) == methods.end())
1343 methods.emplace_back(method_final);
1348 void validate_bp() {
1351 validate_bp(blueprints_, blueprint_mw);
1356 for (
unsigned i = 0; i < blueprints.size(); i++)
1360 if (blueprint->is_added())
continue;
1362 if (blueprint->static_dir_ ==
"" && blueprint->all_rules_.empty())
1364 std::vector<HTTPMethod> methods;
1365 get_recursive_child_methods(blueprint, methods);
1366 for (HTTPMethod x : methods)
1368 int i =
static_cast<int>(x);
1369 per_methods_[i].trie.add(blueprint->prefix(), 0, blueprint->prefix().length(), i);
1373 current_mw.merge_back(blueprint->mw_indices_);
1374 for (
auto& rule : blueprint->all_rules_)
1376 if (rule && !rule->is_added())
1378 auto upgraded = rule->upgrade();
1380 rule = std::move(upgraded);
1382 rule->mw_indices_.merge_front(current_mw);
1383 internal_add_rule_object(rule->rule(), rule.get(), i, blueprints);
1386 validate_bp(blueprint->blueprints_, current_mw);
1387 current_mw.pop_back(blueprint->mw_indices_);
1388 blueprint->set_added();
1394 for (
auto& rule : all_rules_)
1396 if (rule && !rule->is_added())
1398 auto upgraded = rule->upgrade();
1400 rule = std::move(upgraded);
1402 internal_add_rule_object(rule->rule(), rule.get());
1405 for (
auto& per_method : per_methods_)
1407 per_method.trie.validate();
1412 template<
typename Adaptor>
1413 void handle_upgrade(
const request& req,
response& res, Adaptor&& adaptor)
1415 if (req.method >= HTTPMethod::InternalMethodCount)
1418 auto& per_method = per_methods_[
static_cast<int>(req.method)];
1419 auto& rules = per_method.rules;
1420 unsigned rule_index = per_method.trie.find(req.
url).rule_index;
1424 for (
auto& per_method : per_methods_)
1426 if (per_method.trie.find(req.
url).rule_index)
1428 CROW_LOG_DEBUG <<
"Cannot match method " << req.
url <<
" " << method_name(req.method);
1435 CROW_LOG_INFO <<
"Cannot match rules " << req.
url;
1441 if (rule_index >= rules.size())
1442 throw std::runtime_error(
"Trie internal structure corrupted!");
1444 if (rule_index == RULE_SPECIAL_REDIRECT_SLASH)
1446 CROW_LOG_INFO <<
"Redirecting to a url with trailing slash: " << req.
url;
1450 if (req.get_header_value(
"Host").empty())
1456 res.
add_header(
"Location",
"http://" + req.get_header_value(
"Host") + req.
url +
"/");
1462 CROW_LOG_DEBUG <<
"Matched rule (upgrade) '" << rules[rule_index]->rule_ <<
"' " <<
static_cast<uint32_t
>(req.method) <<
" / " << rules[rule_index]->get_methods();
1466 rules[rule_index]->handle_upgrade(req, res, std::move(adaptor));
1470 exception_handler_(res);
1476 void get_found_bp(std::vector<uint16_t>& bp_i, std::vector<Blueprint*>& blueprints, std::vector<Blueprint*>& found_bps, uint16_t index = 0)
1486 auto verify_prefix = [&bp_i, &index, &blueprints, &found_bps]() {
1488 bp_i[index] < blueprints.size() &&
1489 blueprints[bp_i[index]]->prefix().substr(0, found_bps[index - 1]->prefix().length() + 1).compare(std::string(found_bps[index - 1]->prefix() +
'/')) == 0;
1491 if (index < bp_i.size())
1494 if (verify_prefix())
1496 found_bps.push_back(blueprints[bp_i[index]]);
1497 get_found_bp(bp_i, found_bps.back()->blueprints_, found_bps, ++index);
1501 if (found_bps.size() < 2)
1504 found_bps.push_back(blueprints_[bp_i[index]]);
1508 found_bps.pop_back();
1509 Blueprint* last_element = found_bps.back();
1510 found_bps.push_back(last_element->blueprints_[bp_i[index]]);
1512 get_found_bp(bp_i, found_bps.back()->blueprints_, found_bps, ++index);
1521 std::vector<Blueprint*> bps_found;
1522 get_found_bp(found.blueprint_indices, blueprints_, bps_found);
1523 for (
int i = bps_found.size() - 1; i > 0; i--)
1525 std::vector<uint16_t> bpi = found.blueprint_indices;
1526 if (bps_found[i]->catchall_rule().has_handler())
1530 bps_found[i]->catchall_rule().handler_(req, res);
1534 exception_handler_(res);
1536#ifdef CROW_ENABLE_DEBUG
1537 return std::string(
"Redirected to Blueprint \"" + bps_found[i]->prefix() +
"\" Catchall rule");
1539 return std::string();
1543 if (catchall_rule_.has_handler())
1547 catchall_rule_.handler_(req, res);
1551 exception_handler_(res);
1553#ifdef CROW_ENABLE_DEBUG
1554 return std::string(
"Redirected to global Catchall rule");
1556 return std::string();
1559 return std::string();
1562 std::unique_ptr<routing_handle_result> handle_initial(
request& req,
response& res)
1564 HTTPMethod method_actual = req.method;
1566 std::unique_ptr<routing_handle_result> found{
1569 std::vector<uint16_t>(),
1571 HTTPMethod::InternalMethodCount)};
1574 if (CROW_UNLIKELY(req.method >= HTTPMethod::InternalMethodCount))
1576 else if (req.method == HTTPMethod::Head)
1578 *found = per_methods_[
static_cast<int>(method_actual)].trie.find(req.
url);
1580 if (!found->rule_index)
1582 method_actual = HTTPMethod::Get;
1583 *found = per_methods_[
static_cast<int>(method_actual)].trie.find(req.
url);
1584 if (!found->rule_index)
1586 CROW_LOG_DEBUG <<
"Cannot match rules " << req.
url;
1587 res = response(404);
1594 found->method = method_actual;
1597 else if (req.method == HTTPMethod::Options)
1599 std::string allow =
"OPTIONS, HEAD, ";
1601 if (req.
url ==
"/*")
1603 for (
int i = 0; i < static_cast<int>(HTTPMethod::InternalMethodCount); i++)
1605 if (
static_cast<int>(HTTPMethod::Head) == i)
1608 if (!per_methods_[i].trie.is_empty())
1610 allow += method_name(
static_cast<HTTPMethod
>(i)) +
", ";
1613 allow = allow.substr(0, allow.size() - 2);
1614 res = response(204);
1617 found->method = method_actual;
1622 bool rules_matched =
false;
1623 for (
int i = 0; i < static_cast<int>(HTTPMethod::InternalMethodCount); i++)
1625 if (per_methods_[i].trie.find(req.
url).rule_index)
1627 rules_matched =
true;
1629 if (
static_cast<int>(HTTPMethod::Head) == i)
1632 allow += method_name(
static_cast<HTTPMethod
>(i)) +
", ";
1637 allow = allow.substr(0, allow.size() - 2);
1638 res = response(204);
1641 found->method = method_actual;
1646 CROW_LOG_DEBUG <<
"Cannot match rules " << req.
url;
1647 res = response(404);
1655 *found = per_methods_[
static_cast<int>(method_actual)].trie.find(req.
url);
1657 if (!found->rule_index)
1659 for (
auto& per_method : per_methods_)
1661 if (per_method.trie.find(req.
url).rule_index)
1663 const std::string error_message(
get_error(405, *found, req, res));
1664 CROW_LOG_DEBUG <<
"Cannot match method " << req.
url <<
" " << method_name(method_actual) <<
". " << error_message;
1671 const std::string error_message(
get_error(404, *found, req, res));
1672 CROW_LOG_DEBUG <<
"Cannot match rules " << req.
url <<
". " << error_message;
1677 found->method = method_actual;
1682 template<
typename App>
1683 void handle(request& req, response& res, routing_handle_result found)
1685 HTTPMethod method_actual = found.method;
1686 auto& rules = per_methods_[
static_cast<int>(method_actual)].rules;
1687 unsigned rule_index = found.rule_index;
1689 if (rule_index >= rules.size())
1690 throw std::runtime_error(
"Trie internal structure corrupted!");
1692 if (rule_index == RULE_SPECIAL_REDIRECT_SLASH)
1694 CROW_LOG_INFO <<
"Redirecting to a url with trailing slash: " << req.url;
1695 res = response(301);
1698 if (req.get_header_value(
"Host").empty())
1700 res.add_header(
"Location", req.url +
"/");
1704 res.add_header(
"Location",
"http://" + req.get_header_value(
"Host") + req.url +
"/");
1710 CROW_LOG_DEBUG <<
"Matched rule '" << rules[rule_index]->rule_ <<
"' " <<
static_cast<uint32_t
>(req.method) <<
" / " << rules[rule_index]->get_methods();
1714 auto& rule = rules[rule_index];
1715 handle_rule<App>(rule, req, res, found.r_params);
1719 exception_handler_(res);
1725 template<
typename App>
1726 typename std::enable_if<std::tuple_size<typename App::mw_container_t>::value != 0,
void>::type
1729 if (!rule->mw_indices_.empty())
1731 auto& ctx = *
reinterpret_cast<typename App::context_t*
>(req.middleware_context);
1732 auto& container = *
reinterpret_cast<typename App::mw_container_t*
>(req.middleware_container);
1733 detail::middleware_call_criteria_dynamic<false> crit_fwd(rule->mw_indices_.indices());
1735 auto glob_completion_handler = std::move(res.complete_request_handler_);
1736 res.complete_request_handler_ = [] {};
1738 detail::middleware_call_helper<
decltype(crit_fwd),
1739 0,
typename App::context_t,
typename App::mw_container_t>(crit_fwd, container, req, res, ctx);
1743 glob_completion_handler();
1747 res.complete_request_handler_ = [&rule, &ctx, &container, &req, &res, glob_completion_handler] {
1748 detail::middleware_call_criteria_dynamic<true> crit_bwd(rule->mw_indices_.indices());
1750 detail::after_handlers_call_helper<
1752 std::tuple_size<typename App::mw_container_t>::value - 1,
1753 typename App::context_t,
1754 typename App::mw_container_t>(crit_bwd, container, ctx, req, res);
1755 glob_completion_handler();
1758 rule->handle(req, res, rp);
1761 template<
typename App>
1762 typename std::enable_if<std::tuple_size<typename App::mw_container_t>::value == 0,
void>::type
1765 rule->handle(req, res, rp);
1770 for (
int i = 0; i < static_cast<int>(HTTPMethod::InternalMethodCount); i++)
1772 Trie& trie_ = per_methods_[i].trie;
1773 if (!trie_.is_empty())
1775 CROW_LOG_DEBUG << method_name(static_cast<HTTPMethod>(i));
1776 trie_.debug_print();
1781 std::vector<Blueprint*>& blueprints()
1788 return exception_handler_;
1791 static void default_exception_handler(response& res)
1794 res = response(500);
1800 catch (
const std::exception& e)
1802 CROW_LOG_ERROR <<
"An uncaught exception occurred: " << e.what();
1806 CROW_LOG_ERROR <<
"An uncaught exception occurred. The type was unknown so no information was available.";
1811 CatchallRule catchall_rule_;
1815 std::vector<BaseRule*> rules;
1822 std::array<PerMethod, static_cast<int>(HTTPMethod::InternalMethodCount)> per_methods_;
1823 std::vector<std::unique_ptr<BaseRule>> all_rules_;
1824 std::vector<Blueprint*> blueprints_;
1825 std::function<void(
crow::response&)> exception_handler_ = &default_exception_handler;