parse.cc 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417
  1. // Copyright 2020 The Chromium Authors. All rights reserved.
  2. // Copyright 2014 Blake Embrey (hello@blakeembrey.com)
  3. // Use of this source code is governed by an MIT-style license that can be
  4. // found in the LICENSE file or at https://opensource.org/licenses/MIT.
  5. #include "third_party/liburlpattern/parse.h"
  6. #include <unordered_set>
  7. #include "third_party/abseil-cpp/absl/base/macros.h"
  8. #include "third_party/abseil-cpp/absl/strings/str_format.h"
  9. #include "third_party/liburlpattern/pattern.h"
  10. #include "third_party/liburlpattern/tokenize.h"
  11. #include "third_party/liburlpattern/utils.h"
  12. // The following code is a translation from the path-to-regexp typescript at:
  13. //
  14. // https://github.com/pillarjs/path-to-regexp/blob/125c43e6481f68cc771a5af22b914acdb8c5ba1f/src/index.ts#L126-L232
  15. namespace liburlpattern {
  16. namespace {
  17. // Helper class that tracks the parser state.
  18. class State {
  19. public:
  20. State(std::vector<Token> token_list,
  21. EncodeCallback encode_callback,
  22. Options options)
  23. : token_list_(std::move(token_list)),
  24. encode_callback_(std::move(encode_callback)),
  25. options_(std::move(options)),
  26. segment_wildcard_regex_(
  27. absl::StrFormat("[^%s]+?",
  28. EscapeRegexpString(options_.delimiter_list))) {}
  29. // Return true if there are more tokens to process.
  30. bool HasMoreTokens() const { return index_ < token_list_.size(); }
  31. // Attempt to consume the next Token, but only if it matches the given
  32. // |type|. Returns a pointer to the Token on success or nullptr on failure.
  33. const Token* TryConsume(TokenType type) {
  34. ABSL_ASSERT(index_ < token_list_.size());
  35. TokenType next_type = token_list_[index_].type;
  36. if (next_type != type)
  37. return nullptr;
  38. // The last token should always be kEnd.
  39. if ((index_ + 1) == token_list_.size())
  40. ABSL_ASSERT(token_list_[index_].type == TokenType::kEnd);
  41. return &(token_list_[index_++]);
  42. }
  43. // Consume the next Token requiring it to be the given |type|. If this
  44. // is not possible then return an error.
  45. absl::StatusOr<const Token*> MustConsume(TokenType type) {
  46. ABSL_ASSERT(index_ < token_list_.size());
  47. if (const Token* token = TryConsume(type))
  48. return token;
  49. return absl::InvalidArgumentError(absl::StrFormat(
  50. "Unexpected %s '%s' at index %d, expected %s.",
  51. TokenTypeToString(token_list_[index_].type), token_list_[index_].value,
  52. token_list_[index_].index, TokenTypeToString(type)));
  53. }
  54. const Token* TryConsumeModifier() {
  55. const Token* result = TryConsume(TokenType::kOtherModifier);
  56. if (!result)
  57. result = TryConsume(TokenType::kAsterisk);
  58. return result;
  59. }
  60. // Consume as many sequential kChar and kEscapedChar Tokens as possible
  61. // appending them together into a single string value.
  62. std::string ConsumeText() {
  63. // Unfortunately we cannot use a view here and must copy into a new
  64. // string. This is necessary to flatten escape sequences into
  65. // a single value with other characters.
  66. std::string result;
  67. const Token* token = nullptr;
  68. do {
  69. token = TryConsume(TokenType::kChar);
  70. if (!token)
  71. token = TryConsume(TokenType::kEscapedChar);
  72. if (token)
  73. result.append(token->value.data(), token->value.size());
  74. } while (token);
  75. return result;
  76. }
  77. // Append the given Token value to the pending fixed value. This will
  78. // be converted to a kFixed Part when we reach the end of a run of
  79. // kChar and kEscapedChar tokens.
  80. void AppendToPendingFixedValue(absl::string_view token_value) {
  81. pending_fixed_value_.append(token_value.data(), token_value.size());
  82. }
  83. // Convert the pending fixed value, if any, to a kFixed Part. Has no effect
  84. // if there is no pending value.
  85. absl::Status MaybeAddPartFromPendingFixedValue() {
  86. if (pending_fixed_value_.empty())
  87. return absl::OkStatus();
  88. auto encoded_result = encode_callback_(std::move(pending_fixed_value_));
  89. if (!encoded_result.ok())
  90. return encoded_result.status();
  91. part_list_.emplace_back(PartType::kFixed, std::move(encoded_result.value()),
  92. Modifier::kNone);
  93. pending_fixed_value_ = "";
  94. return absl::OkStatus();
  95. }
  96. // Add a Part for the given set of tokens.
  97. absl::Status AddPart(std::string prefix,
  98. const Token* name_token,
  99. const Token* regex_or_wildcard_token,
  100. std::string suffix,
  101. const Token* modifier_token) {
  102. // Convert the modifier Token into a Modifier enum value.
  103. Modifier modifier = Modifier::kNone;
  104. if (modifier_token) {
  105. ABSL_ASSERT(!modifier_token->value.empty());
  106. switch (modifier_token->value[0]) {
  107. case '?':
  108. modifier = Modifier::kOptional;
  109. break;
  110. case '*':
  111. modifier = Modifier::kZeroOrMore;
  112. break;
  113. case '+':
  114. modifier = Modifier::kOneOrMore;
  115. break;
  116. default:
  117. ABSL_ASSERT(false);
  118. break;
  119. }
  120. }
  121. // If this is a `{ ... }` grouping containing only fixed text, then
  122. // just add it to our pending value for now. We want to collect as
  123. // much fixed text as possible in the buffer before commiting it to
  124. // a kFixed Part.
  125. if (!name_token && !regex_or_wildcard_token &&
  126. modifier == Modifier::kNone) {
  127. AppendToPendingFixedValue(prefix);
  128. return absl::OkStatus();
  129. }
  130. // We are about to add some kind of matching group Part to the list.
  131. // Before doing that make sure to flush any pending fixed test to a
  132. // kFixed Part.
  133. absl::Status status = MaybeAddPartFromPendingFixedValue();
  134. if (!status.ok())
  135. return status;
  136. // If there is no name, regex, or wildcard tokens then this is just a fixed
  137. // string grouping; e.g. "{foo}?". The fixed string ends up in the prefix
  138. // value since it consumed the entire text of the grouping. If the prefix
  139. // value is empty then its an empty "{}" group and we return without adding
  140. // any Part.
  141. if (!name_token && !regex_or_wildcard_token) {
  142. ABSL_ASSERT(suffix.empty());
  143. if (prefix.empty())
  144. return absl::OkStatus();
  145. auto result = encode_callback_(std::move(prefix));
  146. if (!result.ok())
  147. return result.status();
  148. part_list_.emplace_back(PartType::kFixed, *result, modifier);
  149. return absl::OkStatus();
  150. }
  151. // Determine the regex value. If there is a |kRegex| Token, then this is
  152. // explicitly set by that Token. If there is a wildcard token, then this
  153. // is set to the |kFullWildcardRegex| constant. Otherwise a kName Token by
  154. // itself gets an implicit regex value that matches through to the end of
  155. // the segment. This is represented by the |segment_wildcard_regex_| value.
  156. std::string regex_value;
  157. if (!regex_or_wildcard_token)
  158. regex_value = segment_wildcard_regex_;
  159. else if (regex_or_wildcard_token->type == TokenType::kAsterisk)
  160. regex_value = kFullWildcardRegex;
  161. else
  162. regex_value = std::string(regex_or_wildcard_token->value);
  163. // Next determine the type of the Part. This depends on the regex value
  164. // since we give certain values special treatment with their own type.
  165. // A |segment_wildcard_regex_| is mapped to the kSegmentWildcard type. A
  166. // |kFullWildcardRegex| is mapped to the kFullWildcard type. Otherwise
  167. // the Part gets the kRegex type.
  168. PartType type = PartType::kRegex;
  169. if (regex_value == segment_wildcard_regex_) {
  170. type = PartType::kSegmentWildcard;
  171. regex_value = "";
  172. } else if (regex_value == kFullWildcardRegex) {
  173. type = PartType::kFullWildcard;
  174. regex_value = "";
  175. }
  176. // Every kRegex, kSegmentWildcard, and kFullWildcard Part must have a
  177. // group name. If there was a kName Token, then use the explicitly
  178. // set name. Otherwise we generate a numeric based key for the name.
  179. std::string name;
  180. if (name_token)
  181. name = std::string(name_token->value);
  182. else if (regex_or_wildcard_token)
  183. name = GenerateKey();
  184. auto name_set_result = name_set_.insert(name);
  185. if (!name_set_result.second) {
  186. return absl::InvalidArgumentError(
  187. absl::StrFormat("Duplicate group name '%s' at index %d.", name,
  188. token_list_[index_].index));
  189. }
  190. auto prefix_result = encode_callback_(std::move(prefix));
  191. if (!prefix_result.ok())
  192. return prefix_result.status();
  193. auto suffix_result = encode_callback_(std::move(suffix));
  194. if (!suffix_result.ok())
  195. return suffix_result.status();
  196. // Finally add the part to the list. We encode the prefix and suffix, but
  197. // must be careful not to encode the regex value since it can change the
  198. // meaning of the regular expression.
  199. part_list_.emplace_back(type, std::move(name), *prefix_result,
  200. std::move(regex_value), *suffix_result, modifier);
  201. return absl::OkStatus();
  202. }
  203. Pattern TakeAsPattern() {
  204. return Pattern(std::move(part_list_), std::move(options_),
  205. std::move(segment_wildcard_regex_));
  206. }
  207. private:
  208. // Generate a numeric key string to be used for groups that do not
  209. // have an explicit kName Token.
  210. std::string GenerateKey() { return absl::StrFormat("%d", next_key_++); }
  211. // The input list of Token objects to process.
  212. const std::vector<Token> token_list_;
  213. EncodeCallback encode_callback_;
  214. // The set of options used to parse and construct this Pattern. This
  215. // controls the behavior of things like kSegmentWildcard parts, etc.
  216. Options options_;
  217. // The special regex value corresponding to the default regex value
  218. // given to a lone kName Token. This is a variable since its value
  219. // is dependent on the |delimiter_list| passed to the constructor.
  220. const std::string segment_wildcard_regex_;
  221. // The output list of Pattern Part objects.
  222. std::vector<Part> part_list_;
  223. // Tracks which names have been seen before so we can error on duplicates.
  224. std::unordered_set<std::string> name_set_;
  225. // A buffer of kChar and kEscapedChar values that are pending the creation
  226. // of a kFixed Part.
  227. std::string pending_fixed_value_;
  228. // The index of the next Token in |token_list_|.
  229. size_t index_ = 0;
  230. // The next value to use when generating a numeric based name for Parts
  231. // without explicit kName Tokens.
  232. int next_key_ = 0;
  233. };
  234. } // namespace
  235. absl::StatusOr<Pattern> Parse(absl::string_view pattern,
  236. EncodeCallback encode_callback,
  237. const Options& options) {
  238. auto result = Tokenize(pattern);
  239. if (!result.ok())
  240. return result.status();
  241. State state(std::move(result.value()), std::move(encode_callback), options);
  242. while (state.HasMoreTokens()) {
  243. // Look for the sequence: <prefix char><name><regex><modifier>
  244. // There could be from zero to all through of these tokens. For
  245. // example:
  246. // * "/:foo(bar)?" - all four tokens
  247. // * "/" - just a char token
  248. // * ":foo" - just a name token
  249. // * "(bar)" - just a regex token
  250. // * "/:foo" - char and name tokens
  251. // * "/(bar)" - char and regex tokens
  252. // * "/:foo?" - char, name, and modifier tokens
  253. // * "/(bar)?" - char, regex, and modifier tokens
  254. const Token* char_token = state.TryConsume(TokenType::kChar);
  255. const Token* name_token = state.TryConsume(TokenType::kName);
  256. const Token* regex_or_wildcard_token = state.TryConsume(TokenType::kRegex);
  257. // If there is no name or regex token, then we may have a wildcard `*`
  258. // token in place of an unnamed regex token. Each wildcard will be
  259. // treated as being equivalent to a "(.*)" regex token. For example:
  260. // * "/*" - equivalent to "/(.*)"
  261. // * "/*?" - equivalent to "/(.*)?"
  262. if (!name_token && !regex_or_wildcard_token)
  263. regex_or_wildcard_token = state.TryConsume(TokenType::kAsterisk);
  264. // If there is a name, regex, or wildcard token then we need to add a
  265. // Pattern Part immediately.
  266. if (name_token || regex_or_wildcard_token) {
  267. // Determine if the char token is a valid prefix. Only characters in the
  268. // configured prefix_list are automatically treated as prefixes. A
  269. // kEscapedChar Token is never treated as a prefix.
  270. absl::string_view prefix = char_token ? char_token->value : "";
  271. if (options.prefix_list.find(prefix.data(), /*pos=*/0, prefix.size()) ==
  272. std::string::npos) {
  273. // This is not a prefix character. Add it to the buffered characters
  274. // to be added as a kFixed Part later.
  275. state.AppendToPendingFixedValue(prefix);
  276. prefix = absl::string_view();
  277. }
  278. // If we have any buffered characters in a pending fixed value, then
  279. // convert them into a kFixed Part now.
  280. absl::Status status = state.MaybeAddPartFromPendingFixedValue();
  281. if (!status.ok())
  282. return status;
  283. // kName and kRegex tokens can optionally be followed by a modifier.
  284. const Token* modifier_token = state.TryConsumeModifier();
  285. // Add the Part for the name and regex/wildcard tokens.
  286. status = state.AddPart(std::string(prefix), name_token,
  287. regex_or_wildcard_token,
  288. /*suffix=*/"", modifier_token);
  289. if (!status.ok())
  290. return status;
  291. continue;
  292. }
  293. // There was neither a kRegex or kName token, so consider if we just have a
  294. // fixed string part. A fixed string can consist of kChar or kEscapedChar
  295. // tokens. These just get added to the buffered pending fixed value for
  296. // now. It will get converted to a kFixed Part later.
  297. const Token* fixed_token = char_token;
  298. if (!fixed_token)
  299. fixed_token = state.TryConsume(TokenType::kEscapedChar);
  300. if (fixed_token) {
  301. state.AppendToPendingFixedValue(fixed_token->value);
  302. continue;
  303. }
  304. // There was not a kChar or kEscapedChar token, so we no we are at the end
  305. // of any fixed string. Do not yet convert the pending fixed value into
  306. // a kFixedPart, though. Its possible there will be further fixed text in
  307. // a `{ ... }` group, etc.
  308. // Look for the sequence:
  309. //
  310. // <open><char prefix><name><regex><char suffix><close><modifier>
  311. //
  312. // The open and close are required, but the other tokens are optional.
  313. // For example:
  314. // * "{a:foo(.*)b}?" - all tokens present
  315. // * "{:foo}?" - just name and modifier tokens
  316. // * "{(.*)}?" - just regex and modifier tokens
  317. // * "{ab}?" - just char and modifier tokens
  318. const Token* open_token = state.TryConsume(TokenType::kOpen);
  319. if (open_token) {
  320. std::string prefix = state.ConsumeText();
  321. const Token* name_token = state.TryConsume(TokenType::kName);
  322. const Token* regex_or_wildcard_token =
  323. state.TryConsume(TokenType::kRegex);
  324. // If there is no name or regex token, then we may have a wildcard `*`
  325. // token in place of an unnamed regex token. Each wildcard will be
  326. // treated as being equivalent to a "(.*)" regex token. For example,
  327. // "{a*b}" is equivalent to "{a(.*)b}".
  328. if (!name_token && !regex_or_wildcard_token)
  329. regex_or_wildcard_token = state.TryConsume(TokenType::kAsterisk);
  330. std::string suffix = state.ConsumeText();
  331. auto result = state.MustConsume(TokenType::kClose);
  332. if (!result.ok())
  333. return result.status();
  334. const Token* modifier_token = state.TryConsumeModifier();
  335. absl::Status status =
  336. state.AddPart(std::move(prefix), name_token, regex_or_wildcard_token,
  337. std::move(suffix), modifier_token);
  338. if (!status.ok())
  339. return status;
  340. continue;
  341. }
  342. // We are about to end the pattern string, so flush any pending text to
  343. // a kFixed Part.
  344. absl::Status status = state.MaybeAddPartFromPendingFixedValue();
  345. if (!status.ok())
  346. return status;
  347. // We didn't find any tokens allowed by the syntax, so we should be
  348. // at the end of the token list. If there is a syntax error, this
  349. // is where it will typically be caught.
  350. auto result = state.MustConsume(TokenType::kEnd);
  351. if (!result.ok())
  352. return result.status();
  353. }
  354. return state.TakeAsPattern();
  355. }
  356. } // namespace liburlpattern