Line data    Source code

       1              : #ifndef THINGER_HTTP_ROUTE_PATTERN_HPP
       2              : #define THINGER_HTTP_ROUTE_PATTERN_HPP
       3              : 
       4              : #include <bitset>
       5              : #include <cstdint>
       6              : #include <optional>
       7              : #include <regex>
       8              : #include <span>
       9              : #include <string>
      10              : #include <string_view>
      11              : #include <vector>
      12              : #include <boost/container/small_vector.hpp>
      13              : 
      14              : namespace thinger::http::detail {
      15              : 
      16              : // Part of a route pattern: literal text, or a parameter (:name or :name(regex))
      17              : struct pattern_token {
      18              :     bool parameter = false;
      19              :     std::string text;   // literal text, or parameter name
      20              :     std::string regex;  // parameter regex, empty for :name (any non-empty text without '/')
      21              : };
      22              : 
      23              : // Split a route pattern into literal text and parameters. A parameter is ':' followed by
      24              : // a name ([a-zA-Z_][a-zA-Z0-9_]*) and, optionally, a regex in balanced parentheses.
      25              : // Throws std::invalid_argument if the parentheses of a parameter regex are not balanced.
      26              : std::vector<pattern_token> parse_route_pattern(std::string_view pattern);
      27              : 
      28              : // Whether a parameter regex depends on the text around it: anchors (^, $), word
      29              : // boundaries, lookaheads or back-references
      30              : bool regex_depends_on_context(std::string_view regex);
      31              : 
      32              : // Regex matching the tokens, a capture group per parameter (and the groups of their regexes)
      33              : std::string pattern_regex(std::span<const pattern_token> tokens);
      34              : 
      35              : // Values captured while matching a path, one per parameter, in order. A capture with no
      36              : // data (default constructed) is a parameter that did not participate in the match.
      37              : using route_captures = boost::container::small_vector<std::string_view, 8>;
      38              : 
      39              : // Matcher of a sequence of tokens: one path segment (between slashes), or the rest of the
      40              : // path from a segment on. Parameter regexes made of characters, character classes and
      41              : // quantifiers (e.g. [a-zA-Z0-9_-]{1,32}, [0-9]+, .+, a UUID) are compiled to a sequence
      42              : // of character sets with repetitions, and a lone parameter with alternative words
      43              : // (e.g. properties|buckets) to the list of words, both matched without std::regex; any
      44              : // other regex (groups, anchors...) makes the matcher fall back to std::regex.
      45              : class path_matcher {
      46              : public:
      47              :     explicit path_matcher(std::span<const pattern_token> tokens);
      48              : 
      49              :     // Whether the whole text matches; on success, appends a capture per parameter
      50              :     bool match(std::string_view text, route_captures& captures) const;
      51              : 
      52              :     // Whether a match may include '/' (so it may span several path segments)
      53         2091 :     bool may_match_slash() const { return may_match_slash_; }
      54              : 
      55              :     // A single parameter that may match '/', as :path(.+): matches the rest of the path
      56         2505 :     bool is_catch_all() const { return catch_all_; }
      57              : 
      58              :     // Regex of the tokens, without parameter names: matchers with the same key match
      59              :     // the same texts
      60          840 :     const std::string& key() const { return key_; }
      61              : 
      62              :     // Whether some text may match both matchers: false only when they cannot start with
      63              :     // the same character (a cheap check, true when in doubt)
      64              :     bool may_overlap(const path_matcher& other) const;
      65              : 
      66              : private:
      67              :     static constexpr uint32_t unbounded = UINT32_MAX;
      68              : 
      69              :     // A character of a set, repeated between min and max times
      70              :     struct atom {
      71              :         std::bitset<256> chars;
      72              :         uint32_t min = 1;
      73              :         uint32_t max = 1;
      74              :     };
      75              : 
      76              :     // Parameter matching the atoms [first, last)
      77              :     struct group {
      78              :         uint16_t first;
      79              :         uint16_t last;
      80              :     };
      81              : 
      82              :     static constexpr size_t max_atoms = 64;
      83              : 
      84              :     // Characters a match may start with (all of them if unknown, or if it may be empty)
      85              :     std::bitset<256> first_chars() const;
      86              : 
      87              :     static bool compile_regex(std::string_view regex, std::vector<atom>& atoms);
      88              :     bool match_atoms(size_t index, size_t position, std::string_view text, size_t* starts) const;
      89              : 
      90              :     std::string key_;
      91              :     bool may_match_slash_ = false;
      92              :     bool catch_all_ = false;
      93              : 
      94              :     // Compiled forms
      95              :     std::vector<atom> atoms_;
      96              :     std::vector<group> groups_;
      97              :     std::optional<std::vector<std::string>> words_;
      98              : 
      99              :     // Fallback, with the capture group of each parameter
     100              :     std::optional<std::regex> regex_;
     101              :     std::vector<size_t> regex_groups_;
     102              : };
     103              : 
     104              : } // namespace thinger::http::detail
     105              : 
     106              : #endif // THINGER_HTTP_ROUTE_PATTERN_HPP