Line data    Source code

       1             : #include "source/extensions/path/uri_template_lib/uri_template_internal.h"
       2             : 
       3             : #include <optional>
       4             : #include <string>
       5             : #include <type_traits>
       6             : #include <variant>
       7             : #include <vector>
       8             : 
       9             : #include "absl/container/flat_hash_set.h"
      10             : #include "absl/flags/flag.h"
      11             : #include "absl/functional/function_ref.h"
      12             : #include "absl/status/status.h"
      13             : #include "absl/status/statusor.h"
      14             : #include "absl/strings/match.h"
      15             : #include "absl/strings/str_cat.h"
      16             : #include "absl/strings/str_join.h"
      17             : #include "absl/strings/str_replace.h"
      18             : #include "absl/strings/str_split.h"
      19             : #include "absl/strings/string_view.h"
      20             : #include "absl/types/variant.h"
      21             : #include "re2/re2.h"
      22             : 
      23             : namespace Envoy {
      24             : namespace Extensions {
      25             : namespace UriTemplate {
      26             : 
      27             : namespace Internal {
      28             : 
      29             : namespace {
      30             : 
      31             : #ifndef SWIG
      32             : // Silence warnings about missing initializers for members of LazyRE2.
      33             : #pragma GCC diagnostic ignored "-Wmissing-field-initializers"
      34             : #endif
      35             : 
      36             : constexpr unsigned long kPatternMatchingMaxVariablesPerPath = 5;
      37             : constexpr unsigned long kPatternMatchingMaxVariableNameLen = 16;
      38             : constexpr unsigned long kPatternMatchingMinVariableNameLen = 1;
      39             : 
      40             : // Valid pchar from https://datatracker.ietf.org/doc/html/rfc3986#appendix-A
      41             : constexpr absl::string_view kLiteral = "a-zA-Z0-9-._~" // Unreserved
      42             :                                        "%"             // pct-encoded
      43             :                                        "!$&'()+,;"     // sub-delims excluding *=
      44             :                                        ":@"
      45             :                                        "="; // user included "=" allowed
      46             : 
      47             : // Default operator used for the variable when none specified.
      48             : constexpr Operator kDefaultVariableOperator = Operator::PathGlob;
      49             : 
      50             : // Visitor for displaying debug info of a ParsedSegment/Variable.var_match.
      51             : struct ToStringVisitor {
      52             :   template <typename T> std::string operator()(const T& val) const;
      53             : };
      54             : 
      55             : // Formatter used to allow joining variants together with StrJoin.
      56             : struct ToStringFormatter {
      57           0 :   template <typename T> void operator()(std::string* out, const T& t) const {
      58           0 :     absl::StrAppend(out, absl::visit(ToStringVisitor(), t));
      59           0 :   }
      60             : };
      61             : 
      62             : // Visitor for converting a ParsedSegment variant to the regex.
      63             : struct ToRegexPatternVisitor {
      64         882 :   template <typename T> std::string operator()(const T& val) const { return toRegexPattern(val); }
      65             : };
      66             : 
      67             : // Formatter used to allow joining variants together with StrJoin.
      68             : struct ToRegexPatternFormatter {
      69         882 :   template <typename T> void operator()(std::string* out, const T& t) const {
      70         882 :     absl::StrAppend(out, absl::visit(ToRegexPatternVisitor(), t));
      71         882 :   }
      72             : };
      73             : 
      74           0 : std::string toString(const Literal val) { return std::string(val); }
      75             : 
      76           0 : std::string toString(const Operator val) {
      77           0 :   switch (val) {
      78           0 :   case Operator::PathGlob:
      79           0 :     return "*";
      80           0 :   case Operator::TextGlob:
      81           0 :     return "**";
      82           0 :   }
      83           0 :   return "";
      84           0 : }
      85             : 
      86           0 : std::string toString(const Variable val) {
      87           0 :   if (val.match_.empty()) {
      88           0 :     return absl::StrCat("{", val.name_, "}");
      89           0 :   }
      90             : 
      91           0 :   return absl::StrCat("{", val.name_, "=", absl::StrJoin(val.match_, "/", ToStringFormatter()),
      92           0 :                       "}");
      93           0 : }
      94             : 
      95           0 : template <typename T> std::string ToStringVisitor::operator()(const T& val) const {
      96           0 :   return toString(val);
      97           0 : }
      98             : 
      99             : template <typename T>
     100             : absl::StatusOr<T>
     101             : alsoUpdatePattern(absl::FunctionRef<absl::StatusOr<ParsedResult<T>>(absl::string_view)> parse_func,
     102        1354 :                   absl::string_view* patt) {
     103             : 
     104        1354 :   absl::StatusOr<ParsedResult<T>> status = parse_func(*patt);
     105        1354 :   if (!status.ok()) {
     106          73 :     return status.status();
     107          73 :   }
     108        1281 :   ParsedResult<T> result = *std::move(status);
     109             : 
     110        1281 :   *patt = result.unparsed_pattern_;
     111        1281 :   return result.parsed_value_;
     112        1354 : }
     113             : 
     114             : } // namespace
     115             : 
     116           0 : std::string Variable::debugString() const { return toString(*this); }
     117             : 
     118           0 : std::string ParsedPathPattern::debugString() const {
     119           0 :   return absl::StrCat("/", absl::StrJoin(parsed_segments_, "/", ToStringFormatter()), suffix_);
     120           0 : }
     121             : 
     122         660 : bool isValidLiteral(absl::string_view literal) {
     123         660 :   static const std::string* kValidLiteralRegex =
     124         660 :       new std::string(absl::StrCat("^[", kLiteral, "]+$"));
     125         660 :   static const LazyRE2 literal_regex = {kValidLiteralRegex->data()};
     126         660 :   return RE2::FullMatch(literal, *literal_regex);
     127         660 : }
     128             : 
     129         720 : bool isValidRewriteLiteral(absl::string_view literal) {
     130         720 :   static const std::string* kValidLiteralRegex =
     131         720 :       new std::string(absl::StrCat("^[", kLiteral, "/]+$"));
     132         720 :   static const LazyRE2 literal_regex = {kValidLiteralRegex->data()};
     133         720 :   return RE2::FullMatch(literal, *literal_regex);
     134         720 : }
     135             : 
     136        1107 : bool isValidVariableName(absl::string_view variable) {
     137        1107 :   static const LazyRE2 variable_regex = {"^[a-zA-Z][a-zA-Z0-9_]*$"};
     138        1107 :   return RE2::FullMatch(variable, *variable_regex);
     139        1107 : }
     140             : 
     141         660 : absl::StatusOr<ParsedResult<Literal>> parseLiteral(absl::string_view pattern) {
     142         660 :   absl::string_view literal =
     143         660 :       std::vector<absl::string_view>(absl::StrSplit(pattern, absl::MaxSplits('/', 1)))[0];
     144         660 :   absl::string_view unparsed_pattern = pattern.substr(literal.size());
     145         660 :   if (!isValidLiteral(literal)) {
     146          45 :     return absl::InvalidArgumentError("Invalid literal");
     147          45 :   }
     148         615 :   return ParsedResult<Literal>(literal, unparsed_pattern);
     149         660 : }
     150             : 
     151         129 : absl::StatusOr<ParsedResult<Operator>> parseOperator(absl::string_view pattern) {
     152         129 :   if (absl::StartsWith(pattern, "**")) {
     153          43 :     return ParsedResult<Operator>(Operator::TextGlob, pattern.substr(2));
     154          43 :   }
     155          86 :   if (absl::StartsWith(pattern, "*")) {
     156          86 :     return ParsedResult<Operator>(Operator::PathGlob, pattern.substr(1));
     157          86 :   }
     158           0 :   return absl::InvalidArgumentError("Invalid Operator");
     159          86 : }
     160             : 
     161         565 : absl::StatusOr<ParsedResult<Variable>> parseVariable(absl::string_view pattern) {
     162             :   // Locate the variable pattern to parse.
     163         565 :   if (pattern.size() < 2 || (pattern)[0] != '{') {
     164           2 :     return absl::InvalidArgumentError("Invalid variable");
     165           2 :   }
     166         563 :   std::vector<absl::string_view> parts = absl::StrSplit(pattern.substr(1), absl::MaxSplits('}', 1));
     167         563 :   if (parts.size() != 2) {
     168           7 :     return absl::InvalidArgumentError("Unmatched variable bracket");
     169           7 :   }
     170         556 :   absl::string_view unparsed_pattern = parts[1];
     171             : 
     172             :   // Parse the actual variable pattern, starting with the variable name.
     173         556 :   std::vector<absl::string_view> variable_parts = absl::StrSplit(parts[0], absl::MaxSplits('=', 1));
     174         556 :   if (!isValidVariableName(variable_parts[0])) {
     175          10 :     return absl::InvalidArgumentError("Invalid variable name");
     176          10 :   }
     177         546 :   Variable var = Variable(variable_parts[0], {});
     178             : 
     179             :   // Parse the variable match pattern (if any).
     180         546 :   if (variable_parts.size() < 2) {
     181         437 :     return ParsedResult<Variable>(var, unparsed_pattern);
     182         437 :   }
     183         109 :   absl::string_view pattern_item = variable_parts[1];
     184         109 :   if (pattern_item.empty()) {
     185           1 :     return absl::InvalidArgumentError("Empty variable match");
     186           1 :   }
     187         266 :   while (!pattern_item.empty()) {
     188         166 :     absl::variant<Operator, Literal> match;
     189         166 :     if (pattern_item[0] == '*') {
     190             : 
     191          78 :       absl::StatusOr<Operator> status = alsoUpdatePattern<Operator>(parseOperator, &pattern_item);
     192          78 :       if (!status.ok()) {
     193           0 :         return status.status();
     194           0 :       }
     195          78 :       match = *std::move(status);
     196             : 
     197         148 :     } else {
     198          88 :       absl::StatusOr<Literal> status = alsoUpdatePattern<Literal>(parseLiteral, &pattern_item);
     199          88 :       if (!status.ok()) {
     200           5 :         return status.status();
     201           5 :       }
     202          83 :       match = *std::move(status);
     203          83 :     }
     204         161 :     var.match_.push_back(match);
     205         161 :     if (!pattern_item.empty()) {
     206          61 :       if (pattern_item[0] != '/' || pattern_item.size() == 1) {
     207           3 :         return absl::InvalidArgumentError("Invalid variable match");
     208           3 :       }
     209          58 :       pattern_item = pattern_item.substr(1);
     210          58 :     }
     211         161 :   }
     212             : 
     213         100 :   return ParsedResult<Variable>(var, unparsed_pattern);
     214         108 : }
     215             : 
     216             : absl::StatusOr<absl::flat_hash_set<absl::string_view>>
     217         236 : gatherCaptureNames(const struct ParsedPathPattern& pattern) {
     218         236 :   absl::flat_hash_set<absl::string_view> captured_variables;
     219             : 
     220         858 :   for (const ParsedSegment& segment : pattern.parsed_segments_) {
     221         858 :     if (!absl::holds_alternative<Variable>(segment)) {
     222         480 :       continue;
     223         480 :     }
     224         378 :     if (captured_variables.size() >= kPatternMatchingMaxVariablesPerPath) {
     225          10 :       return absl::InvalidArgumentError("Exceeded variable count limit");
     226          10 :     }
     227         368 :     absl::string_view name = absl::get<Variable>(segment).name_;
     228             : 
     229         368 :     if (name.size() < kPatternMatchingMinVariableNameLen ||
     230         368 :         name.size() > kPatternMatchingMaxVariableNameLen) {
     231           5 :       return absl::InvalidArgumentError("Invalid variable name length");
     232           5 :     }
     233         363 :     if (captured_variables.contains(name)) {
     234           4 :       return absl::InvalidArgumentError("Repeated variable name");
     235           4 :     }
     236         359 :     captured_variables.emplace(name);
     237         359 :   }
     238             : 
     239         217 :   return captured_variables;
     240         236 : }
     241             : 
     242         217 : absl::Status validateNoOperatorAfterTextGlob(const struct ParsedPathPattern& pattern) {
     243         217 :   bool seen_text_glob = false;
     244         764 :   for (const ParsedSegment& segment : pattern.parsed_segments_) {
     245         764 :     if (absl::holds_alternative<Operator>(segment)) {
     246          36 :       if (seen_text_glob) {
     247           1 :         return absl::InvalidArgumentError("Glob after text glob.");
     248           1 :       }
     249          35 :       seen_text_glob = (absl::get<Operator>(segment) == Operator::TextGlob);
     250         728 :     } else if (absl::holds_alternative<Variable>(segment)) {
     251         298 :       const Variable& var = absl::get<Variable>(segment);
     252         298 :       if (var.match_.empty()) {
     253         214 :         if (seen_text_glob) {
     254             :           // A variable with no explicit matcher is treated as a path glob.
     255           0 :           return absl::InvalidArgumentError("Implicit variable path glob after text glob.");
     256           0 :         }
     257         214 :       } else {
     258         124 :         for (const absl::variant<Operator, absl::string_view>& var_seg : var.match_) {
     259         124 :           if (!absl::holds_alternative<Operator>(var_seg)) {
     260          48 :             continue;
     261          48 :           }
     262          76 :           if (seen_text_glob) {
     263           0 :             return absl::InvalidArgumentError("Glob after text glob.");
     264           0 :           }
     265          76 :           seen_text_glob = (absl::get<Operator>(var_seg) == Operator::TextGlob);
     266          76 :         }
     267          84 :       }
     268         298 :     }
     269         764 :   }
     270         216 :   return absl::OkStatus();
     271         217 : }
     272             : 
     273         362 : absl::StatusOr<ParsedPathPattern> parsePathPatternSyntax(absl::string_view path) {
     274         362 :   struct ParsedPathPattern parsed_pattern;
     275             : 
     276         362 :   static const LazyRE2 printable_regex = {"^/[[:graph:]]*$"};
     277         362 :   if (!RE2::FullMatch(path, *printable_regex)) {
     278          46 :     return absl::InvalidArgumentError("Invalid pattern");
     279          46 :   }
     280             : 
     281             :   // Parse the leading '/'
     282         316 :   path = path.substr(1);
     283             : 
     284             :   // Do the initial lexical parsing.
     285        1314 :   while (!path.empty()) {
     286        1128 :     ParsedSegment segment;
     287        1128 :     if (path[0] == '*') {
     288          51 :       absl::StatusOr<Operator> status = alsoUpdatePattern<Operator>(parseOperator, &path);
     289          51 :       if (!status.ok()) {
     290           0 :         return status.status();
     291           0 :       }
     292          51 :       segment = *std::move(status);
     293        1077 :     } else if (path[0] == '{') {
     294         565 :       absl::StatusOr<Variable> status = alsoUpdatePattern<Variable>(parseVariable, &path);
     295         565 :       if (!status.ok()) {
     296          28 :         return status.status();
     297          28 :       }
     298         537 :       segment = *std::move(status);
     299         580 :     } else {
     300         512 :       absl::StatusOr<Literal> status = alsoUpdatePattern<Literal>(parseLiteral, &path);
     301         512 :       if (!status.ok()) {
     302          24 :         return status.status();
     303          24 :       }
     304         488 :       segment = *std::move(status);
     305         488 :     }
     306        1076 :     parsed_pattern.parsed_segments_.push_back(segment);
     307             : 
     308             :     // Deal with trailing '/' or suffix.
     309        1076 :     if (!path.empty()) {
     310         892 :       if (path == "/") {
     311             :         // Single trailing '/' at the end, mark this with empty literal.
     312          18 :         parsed_pattern.parsed_segments_.emplace_back("");
     313          18 :         break;
     314         874 :       } else if (path[0] == '/') {
     315             :         // Have '/' followed by more text, parse the '/'.
     316         814 :         path = path.substr(1);
     317         814 :       } else {
     318             :         // Not followed by '/', treat as suffix.
     319          60 :         absl::StatusOr<Literal> status = alsoUpdatePattern<Literal>(parseLiteral, &path);
     320          60 :         if (!status.ok()) {
     321          16 :           return status.status();
     322          16 :         }
     323          44 :         parsed_pattern.suffix_ = *std::move(status);
     324          44 :         if (!path.empty()) {
     325             :           // Suffix didn't parse whole remaining pattern ('/' in path).
     326          12 :           return absl::InvalidArgumentError("Prefix match not supported.");
     327          12 :         }
     328          32 :         break;
     329          44 :       }
     330         892 :     }
     331        1076 :   }
     332         236 :   absl::StatusOr<absl::flat_hash_set<absl::string_view>> status =
     333         236 :       gatherCaptureNames(parsed_pattern);
     334         236 :   if (!status.ok()) {
     335          19 :     return status.status();
     336          19 :   }
     337         217 :   parsed_pattern.captured_variables_ = *std::move(status);
     338             : 
     339         217 :   absl::Status validate_status = validateNoOperatorAfterTextGlob(parsed_pattern);
     340         217 :   if (!validate_status.ok()) {
     341           1 :     return validate_status;
     342           1 :   }
     343             : 
     344         216 :   return parsed_pattern;
     345         217 : }
     346             : 
     347         690 : std::string toRegexPattern(absl::string_view pattern) {
     348         690 :   return absl::StrReplaceAll(
     349         690 :       pattern, {{"$", "\\$"}, {"(", "\\("}, {")", "\\)"}, {"+", "\\+"}, {".", "\\."}});
     350         690 : }
     351             : 
     352         324 : std::string toRegexPattern(Operator pattern) {
     353         324 :   static const std::string* kPathGlobRegex = new std::string(absl::StrCat("[", kLiteral, "]+"));
     354         324 :   static const std::string* kTextGlobRegex = new std::string(absl::StrCat("[", kLiteral, "/]*"));
     355         324 :   switch (pattern) {
     356         282 :   case Operator::PathGlob: // "*"
     357         282 :     return *kPathGlobRegex;
     358          42 :   case Operator::TextGlob: // "**"
     359          42 :     return *kTextGlobRegex;
     360         324 :   }
     361           0 :   return "";
     362         324 : }
     363             : 
     364         298 : std::string toRegexPattern(const Variable& pattern) {
     365         298 :   return absl::StrCat("(?P<", pattern.name_, ">",
     366         298 :                       pattern.match_.empty()
     367         298 :                           ? toRegexPattern(kDefaultVariableOperator)
     368         298 :                           : absl::StrJoin(pattern.match_, "/", ToRegexPatternFormatter()),
     369         298 :                       ")");
     370         298 : }
     371             : 
     372         216 : std::string toRegexPattern(const struct ParsedPathPattern& pattern) {
     373         216 :   return absl::StrCat("/", absl::StrJoin(pattern.parsed_segments_, "/", ToRegexPatternFormatter()),
     374         216 :                       toRegexPattern(pattern.suffix_));
     375         216 : }
     376             : 
     377             : } // namespace Internal
     378             : } // namespace UriTemplate
     379             : } // namespace Extensions
     380             : } // namespace Envoy