tlbmc/redfish/routing.cc

#include "tlbmc/redfish/routing.h"

#include <array>
#include <cstddef>
#include <cstdlib>
#include <functional>
#include <memory>
#include <optional>
#include <stdexcept>
#include <string>
#include <string_view>
#include <tuple>
#include <utility>
#include <vector>

#include "absl/log/log.h"
#include "absl/strings/str_cat.h"
#include "absl/time/clock.h"
#include "tlbmc/redfish/common.h"
#include "tlbmc/redfish/query.h"
#include "tlbmc/redfish/request.h"
#include "tlbmc/redfish/response.h"
#include "tlbmc/redfish/verb.h"
#include "tlbmc/trace/tracer.h"

namespace milotic_tlbmc {
namespace crow {

using ::milotic_tlbmc::HttpVerb;
using ::milotic_tlbmc::HttpVerbFromBoost;
using ::milotic_tlbmc::kMaxVerbIndex;
using ::milotic_tlbmc::kMethodNotAllowedIndex;
using ::milotic_tlbmc::RedfishRequest;
using ::milotic_tlbmc::RedfishResponse;

void Trie::OptimizeNode(Node* node) {
  for (size_t x : node->param_children) {
    if (x == 0U) {
      continue;
    }
    Node* child = &nodes_[x];
    OptimizeNode(child);
  }
  if (node->children.empty()) {
    return;
  }
  bool merge_with_child = true;
  for (const Node::ChildMap::value_type& kv : node->children) {
    Node* child = &nodes_[kv.second];
    if (!child->IsSimpleNode()) {
      merge_with_child = false;
      break;
    }
  }
  if (merge_with_child) {
    Node::ChildMap merged;
    for (const Node::ChildMap::value_type& kv : node->children) {
      Node* child = &nodes_[kv.second];
      for (const Node::ChildMap::value_type& child_kv : child->children) {
        merged[kv.first + child_kv.first] = child_kv.second;
      }
    }
    node->children = std::move(merged);
    OptimizeNode(node);
  } else {
    for (const Node::ChildMap::value_type& kv : node->children) {
      Node* child = &nodes_[kv.second];
      OptimizeNode(child);
    }
  }
}

std::pair<unsigned int, RoutingParams> Trie::Find(std::string_view url,
                                                  const Node* node, size_t pos,
                                                  RoutingParams* params) const {
  RoutingParams empty;
  if (params == nullptr) {
    params = &empty;
  }

  unsigned found{};
  RoutingParams match_params;

  if (node == nullptr) {
    node = Head();
  }
  if (pos == url.size()) {
    return {node->rule_index, *params};
  }

  auto update_found = [&found,
                       &match_params](std::pair<unsigned, RoutingParams>& ret) {
    // Current Logic is to choose the rule with the lowest index in the allRules
    // vector
    bool replaceFound = found == 0U || found > ret.first;

    if (ret.first != 0U && replaceFound) {
      found = ret.first;
      match_params = std::move(ret.second);
    }
  };

  for (const Node::ChildMap::value_type& kv : node->children) {
    const std::string& fragment = kv.first;
    const Node* child = &nodes_[kv.second];

    if (url.compare(pos, fragment.size(), fragment) == 0) {
      std::pair<unsigned, RoutingParams> ret =
          Find(url, child, pos + fragment.size(), params);
      update_found(ret);
    }
  }

  if (node->param_children[static_cast<size_t>(ParamType::kString)] != 0U) {
    size_t epos = pos;
    for (; epos < url.size(); epos++) {
      if (url[epos] == '/') {
        break;
      }
    }

    if (epos != pos) {
      params->string_params.emplace_back(url.substr(pos, epos - pos));
      std::pair<unsigned, RoutingParams> ret =
          Find(url,
               &nodes_[node->param_children[static_cast<size_t>(
                   ParamType::kString)]],
               epos, params);
      update_found(ret);
      params->string_params.pop_back();
    }
  }

  return {found, match_params};
}

void Trie::Add(const std::string& url, unsigned int index) {
  size_t idx = 0;

  for (unsigned i = 0; i < url.size(); i++) {
    char c = url[i];
    if (c == '<') {
      constexpr std::array<std::pair<ParamType, std::string_view>, 2>
          param_traits = {
              std::pair<ParamType, std::string_view>{ParamType::kString,
                                                     "<str>"},
              std::pair<ParamType, std::string_view>{ParamType::kString,
                                                     "<string>"},
          };

      for (const std::pair<ParamType, std::string_view>& x : param_traits) {
        if (url.compare(i, x.second.size(), x.second) == 0) {
          size_t index_inner = static_cast<size_t>(x.first);
          if (nodes_[idx].param_children[index_inner] == 0U) {
            unsigned new_node_index = NewNode();
            nodes_[idx].param_children[index_inner] = new_node_index;
          }
          idx = nodes_[idx].param_children[index_inner];
          i += static_cast<unsigned>(x.second.size());
          break;
        }
      }

      i--;
    } else {
      std::string piece(&c, 1);
      if (nodes_[idx].children.count(piece) == 0U) {
        unsigned new_node_index = NewNode();
        nodes_[idx].children.emplace(piece, new_node_index);
      }
      idx = nodes_[idx].children[piece];
    }
  }
  if (nodes_[idx].rule_index != 0U) {
    throw std::runtime_error("handler already exists for " + url);
  }
  nodes_[idx].rule_index = index;
}

void Router::InternalAddRuleObject(const std::string& rule,
                                   BaseRule* rule_object) {
  if (rule_object == nullptr) {
    return;
  }
  for (size_t method = 0; method <= kMethodNotAllowedIndex; method++) {
    if (MethodFieldsContainHttpVerb(rule_object->methods_bit_field_,
                                    static_cast<HttpVerb>(method))) {
      per_methods_[method].rules.push_back(rule_object);
      per_methods_[method].trie.Add(
          rule, static_cast<unsigned>(per_methods_[method].rules.size() - 1U));
      // directory case:
      //   request to `/about' url matches `/about/' rule
      if (rule.size() > 2 && rule.back() == '/') {
        per_methods_[method].trie.Add(
            rule.substr(0, rule.size() - 1),
            static_cast<unsigned>(per_methods_[method].rules.size() - 1));
      }
    }
  }
}

void Router::Validate() {
  for (std::unique_ptr<BaseRule>& rule : all_rules_) {
    if (rule) {
      rule->Validate();
      InternalAddRuleObject(rule->rule_, rule.get());
    }
  }
  for (PerMethod& per_method : per_methods_) {
    per_method.trie.Validate();
  }
}

Router::FindRoute Router::FindRouteByIndex(std::string_view url,
                                           size_t index) const {
  FindRoute route;
  if (index >= per_methods_.size()) {
    return route;
  }
  const PerMethod& per_method = per_methods_[index];
  std::pair<unsigned, RoutingParams> found = per_method.trie.Find(url);
  if (found.first >= per_method.rules.size()) {
    throw std::runtime_error("Trie internal structure corrupted!");
  }
  // Found a 404 route, switch that in
  if (found.first != 0U) {
    route.rule = per_method.rules[found.first];
    route.params = std::move(found.second);
  }
  return route;
}

Router::FindRouteResponse Router::FindRouteByRequest(
    const RedfishRequest& req) const {
  FindRouteResponse find_route;

  std::optional<HttpVerb> verb = HttpVerbFromBoost(req.Method());
  if (!verb) {
    return find_route;
  }
  size_t req_method_index = static_cast<size_t>(*verb);
  // Check to see if this url exists at any verb
  for (size_t per_method_index = 0; per_method_index <= kMaxVerbIndex;
       per_method_index++) {
    // Make sure it's safe to deference the array at that index
    static_assert(kMaxVerbIndex < std::tuple_size_v<decltype(per_methods_)>);
    FindRoute route = FindRouteByIndex(req.Target(), per_method_index);
    if (route.rule == nullptr) {
      continue;
    }
    if (per_method_index == req_method_index) {
      find_route.route = route;
    }
  }
  return find_route;
}

void Router::Handle(const RedfishRequest& req, RedfishResponse& resp) const {
  DLOG(INFO) << "Router Handle: " << req.Target();
  std::optional<HttpVerb> verb = HttpVerbFromBoost(req.Method());
  if (!verb || static_cast<size_t>(*verb) >= per_methods_.size()) {
    resp.SetToNotFound(absl::StrCat("No route found for url: ", req.Target(),
                                    " and method: ", req.Method()));
    resp.End();
    return;
  }

  FindRouteResponse found_route = FindRouteByRequest(req);

  if (found_route.route.rule == nullptr) {
    resp.SetToNotFound(absl::StrCat("No route found for url: ", req.Target(),
                                    " and method: ", req.Method()));
    resp.End();
    return;
  }

  BaseRule& rule = *found_route.route.rule;
  RoutingParams params = std::move(found_route.route.params);
  milotic_tlbmc::Tracer::GetInstance().AddRepeatedDatapoint(
      "Tlbmc-Redfish-Routing-End", absl::Now());
  if (!RedfishPreprocess(req, resp)) {
    return;
  }
  rule.Handle(req, resp, params);

  // Handle Query Parameters
  RedfishPostprocess(smart_router_, std::ref(*this), req, resp);
  resp.End();
}

std::vector<std::pair<std::string_view, size_t>> Router::GetRegisteredRoutes()
    const {
  std::vector<std::pair<std::string_view, size_t>> routes;
  for (const std::unique_ptr<BaseRule>& rule : all_rules_) {
    if (rule) {
      routes.push_back({rule->rule_, rule->methods_bit_field_});
    }
  }
  return routes;
}

}  // namespace crow
}  // namespace milotic_tlbmc