Skip to content
rachel/workerd
File

Blob: src/workerd/jsg/url.c++

77.8 KB
1#include "url.h"
2 
3#include <workerd/util/strings.h>
4 
5#include <kj/hash.h>
6 
7extern "C" {
8#include "ada_c.h"
9}
10#include "ada.h"
11 
12#include <unicode/uchar.h>
13#include <unicode/utf8.h>
14 
15#include <kj/debug.h>
16#include <kj/string-tree.h>
17#include <kj/vector.h>
18 
19#include <algorithm>
20#include <regex>
21#include <string>
22#include <vector>
23 
24namespace workerd::jsg {
25 
26namespace {
27class AdaOwnedStringDisposer: public kj::ArrayDisposer {
28 public:
29  static const AdaOwnedStringDisposer INSTANCE;
30 
31 protected:
32  void disposeImpl(void* firstElement,
33      size_t elementSize,
34      size_t elementCount,
35      size_t capacity,
36      void (*destroyElement)(void*)) const override {
37    ada_owned_string data = {static_cast<const char*>(firstElement), elementCount};
38    ada_free_owned_string(data);
39  }
40};
41const AdaOwnedStringDisposer AdaOwnedStringDisposer::INSTANCE;
42 
43kj::Own<void> wrap(ada_url url) {
44  return kj::disposeWith<ada_free>(url);
45}
46 
47template <typename T>
48T getInner(const kj::Own<void>& inner) {
49  const void* value = inner.get();
50  KJ_DASSERT(value != nullptr);
51  return const_cast<T>(value);
52}
53 
54kj::Array<const char> normalizePathEncoding(kj::ArrayPtr<const char> pathname) {
55  // Sadly, this is a bit tricky because we do not want to decode %2f as a slash.
56  // we want to keep those as is. So we'll split the input around those bits.
57  // Unfortunately we need to split on either %2f or %2F, so we'll need to search
58  // through ourselves. This is simple enough, tho. We'll percent decode as we go,
59  // re-encode the pieces and then join them back together with %2F.
60 
61  static constexpr auto findNext = [](std::string_view input) -> kj::Maybe<size_t> {
62    size_t pos = input.find("%2", 0);
63    if (pos != std::string_view::npos) {
64      if (input[pos + 2] == 'f' || input[pos + 2] == 'F') {
65        return pos;
66      }
67    }
68    return kj::none;
69  };
70 
71  std::string_view input(pathname.begin(), pathname.end());
72  std::vector<std::string> parts;
73 
74  while (true) {
75    if (input.empty()) {
76      parts.emplace_back("");
77      break;
78    }
79    KJ_IF_SOME(pos, findNext(input)) {
80      parts.push_back(ada::unicode::percent_decode(input.substr(0, pos), 0));
81      input = input.substr(pos + 3);
82      continue;
83    } else {
84      // No more %2f or %2F found. Add input to parts
85      parts.push_back(ada::unicode::percent_decode(input, 0));
86      break;
87    }
88  }
89 
90  std::string res;
91  bool first = true;
92  for (auto& part: parts) {
93    auto encoded = ada::unicode::percent_encode(part, ada::character_sets::PATH_PERCENT_ENCODE);
94    if (!first)
95      res += "%2F";
96    else
97      first = false;
98    res += encoded;
99  }
100 
101  kj::Array<const char> ret = kj::heapArray<const char>(res.length());
102  memcpy(const_cast<char*>(ret.begin()), res.data(), res.length());
103  return kj::mv(ret);
104}
105 
106class StringTreeHolder final {
107 public:
108  StringTreeHolder(): tree(kj::strTree()) {}
109  StringTreeHolder(kj::StringTree&& tree): tree(kj::mv(tree)) {}
110  StringTreeHolder(kj::StringPtr ptr): tree(kj::strTree(ptr)) {}
111  StringTreeHolder(kj::String str): tree(kj::strTree(kj::mv(str))) {}
112 
113  template <typename... Params>
114  StringTreeHolder& append(Params&&... params) {
115    // Keep the tree from getting too deeply nested by flattening it out
116    // once the depth gets to a certain point.
117    if (++depth % 2048 == 0) {
118      tree = kj::strTree(tree.flatten(), kj::fwd<Params>(params)...);
119    } else {
120      tree = kj::strTree(kj::mv(tree), kj::fwd<Params>(params)...);
121    }
122    return *this;
123  }
124 
125  operator kj::String() && {
126    return kj::mv(tree).flatten();
127  }
128 
129  operator kj::StringTree() && {
130    return kj::mv(tree);
131  }
132 
133 private:
134  kj::StringTree tree;
135  size_t depth = 0;
136};
137 
138}  // namespace
139 
140Url::Url(kj::Own<void> inner): inner(kj::mv(inner)) {}
141 
142bool Url::operator==(const Url& other) const {
143  return getHref() == other.getHref();
144}
145 
146bool Url::equal(const Url& other, EquivalenceOption option) const {
147  if (option == EquivalenceOption::DEFAULT) {
148    return *this == other;
149  }
150 
151  auto otherPathname = other.getPathname();
152  auto thisPathname = getPathname();
153  kj::Array<const char> otherPathnameStore = nullptr;
154  kj::Array<const char> thisPathnameStore = nullptr;
155 
156  if ((option & EquivalenceOption::NORMALIZE_PATH) == EquivalenceOption::NORMALIZE_PATH) {
157    otherPathnameStore = normalizePathEncoding(otherPathname);
158    otherPathname = otherPathnameStore;
159    thisPathnameStore = normalizePathEncoding(thisPathname);
160    thisPathname = thisPathnameStore;
161  }
162 
163  // If we are ignoring fragments, we'll compare each component separately:
164  return (other.getProtocol() == getProtocol()) && (other.getHost() == getHost()) &&
165      (other.getUsername() == getUsername()) && (other.getPassword() == getPassword()) &&
166      (otherPathname == thisPathname) &&
167      (((option & EquivalenceOption::IGNORE_SEARCH) == EquivalenceOption::IGNORE_SEARCH)
168              ? true
169              : other.getSearch() == getSearch()) &&
170      (((option & EquivalenceOption::IGNORE_FRAGMENTS) == EquivalenceOption::IGNORE_FRAGMENTS)
171              ? true
172              : other.getHash() == getHash());
173}
174 
175bool Url::canParse(kj::StringPtr input, kj::Maybe<kj::StringPtr> base) {
176  return canParse(kj::ArrayPtr<const char>(input), base);
177}
178 
179bool Url::canParse(kj::ArrayPtr<const char> input, kj::Maybe<kj::ArrayPtr<const char>> base) {
180  KJ_IF_SOME(b, base) {
181    return ada_can_parse_with_base(input.begin(), input.size(), b.begin(), b.size());
182  }
183  return ada_can_parse(input.begin(), input.size());
184}
185 
186kj::Maybe<Url> Url::tryParse(kj::StringPtr input, kj::Maybe<kj::StringPtr> base) {
187  return tryParse(kj::ArrayPtr<const char>(input), base);
188}
189 
190kj::Maybe<Url> Url::tryParse(
191    kj::ArrayPtr<const char> input, kj::Maybe<kj::ArrayPtr<const char>> base) {
192  ada_url result = nullptr;
193  KJ_IF_SOME(b, base) {
194    result = ada_parse_with_base(input.begin(), input.size(), b.begin(), b.size());
195  } else {
196    result = ada_parse(input.begin(), input.size());
197  }
198  if (!ada_is_valid(result)) {
199    ada_free(result);
200    return kj::none;
201  }
202  return Url(wrap(result));
203}
204 
205kj::Maybe<Url> Url::resolve(kj::ArrayPtr<const char> input) {
206  return tryParse(input, getHref());
207}
208 
209kj::ArrayPtr<const char> Url::getHref() const {
210  ada_string href = ada_get_href(getInner<ada_url>(inner));
211  return kj::ArrayPtr<const char>(href.data, href.length);
212}
213 
214kj::ArrayPtr<const char> Url::getUsername() const {
215  ada_string username = ada_get_username(getInner<ada_url>(inner));
216  return kj::ArrayPtr<const char>(username.data, username.length);
217}
218 
219kj::ArrayPtr<const char> Url::getPassword() const {
220  ada_string password = ada_get_password(getInner<ada_url>(inner));
221  return kj::ArrayPtr<const char>(password.data, password.length);
222}
223 
224kj::ArrayPtr<const char> Url::getPort() const {
225  ada_string port = ada_get_port(getInner<ada_url>(inner));
226  return kj::ArrayPtr<const char>(port.data, port.length);
227}
228 
229kj::ArrayPtr<const char> Url::getHash() const {
230  ada_string hash = ada_get_hash(getInner<ada_url>(inner));
231  return kj::ArrayPtr<const char>(hash.data, hash.length);
232}
233 
234kj::ArrayPtr<const char> Url::getHost() const {
235  ada_string host = ada_get_host(getInner<ada_url>(inner));
236  return kj::ArrayPtr<const char>(host.data, host.length);
237}
238 
239kj::ArrayPtr<const char> Url::getHostname() const {
240  ada_string hostname = ada_get_hostname(getInner<ada_url>(inner));
241  return kj::ArrayPtr<const char>(hostname.data, hostname.length);
242}
243 
244kj::ArrayPtr<const char> Url::getPathname() const {
245  ada_string path = ada_get_pathname(getInner<ada_url>(inner));
246  return kj::ArrayPtr<const char>(path.data, path.length);
247}
248 
249kj::ArrayPtr<const char> Url::getSearch() const {
250  ada_string search = ada_get_search(getInner<ada_url>(inner));
251  return kj::ArrayPtr<const char>(search.data, search.length);
252}
253 
254kj::ArrayPtr<const char> Url::getProtocol() const {
255  ada_string protocol = ada_get_protocol(getInner<ada_url>(inner));
256  return kj::ArrayPtr<const char>(protocol.data, protocol.length);
257}
258 
259kj::Array<const char> Url::getOrigin() const {
260  ada_owned_string result = ada_get_origin(getInner<ada_url>(inner));
261  return kj::Array<const char>(
262      const_cast<char*>(result.data), result.length, AdaOwnedStringDisposer::INSTANCE);
263}
264 
265bool Url::setHref(kj::ArrayPtr<const char> value) {
266  return ada_set_href(getInner<ada_url>(inner), value.begin(), value.size());
267}
268 
269bool Url::setHost(kj::ArrayPtr<const char> value) {
270  return ada_set_host(getInner<ada_url>(inner), value.begin(), value.size());
271}
272 
273bool Url::setHostname(kj::ArrayPtr<const char> value) {
274  return ada_set_hostname(getInner<ada_url>(inner), value.begin(), value.size());
275}
276 
277bool Url::setProtocol(kj::ArrayPtr<const char> value) {
278  return ada_set_protocol(getInner<ada_url>(inner), value.begin(), value.size());
279}
280 
281bool Url::setUsername(kj::ArrayPtr<const char> value) {
282  return ada_set_username(getInner<ada_url>(inner), value.begin(), value.size());
283}
284 
285bool Url::setPassword(kj::ArrayPtr<const char> value) {
286  return ada_set_password(getInner<ada_url>(inner), value.begin(), value.size());
287}
288 
289bool Url::setPort(kj::Maybe<kj::ArrayPtr<const char>> value) {
290  KJ_IF_SOME(v, value) {
291    return ada_set_port(getInner<ada_url>(inner), v.begin(), v.size());
292  }
293  ada_clear_port(getInner<ada_url>(inner));
294  return true;
295}
296 
297bool Url::setPathname(kj::ArrayPtr<const char> value) {
298  return ada_set_pathname(getInner<ada_url>(inner), value.begin(), value.size());
299}
300 
301void Url::setSearch(kj::Maybe<kj::ArrayPtr<const char>> value) {
302  KJ_IF_SOME(v, value) {
303    return ada_set_search(getInner<ada_url>(inner), v.begin(), v.size());
304  }
305  ada_clear_search(getInner<ada_url>(inner));
306}
307 
308void Url::setHash(kj::Maybe<kj::ArrayPtr<const char>> value) {
309  KJ_IF_SOME(v, value) {
310    return ada_set_hash(getInner<ada_url>(inner), v.begin(), v.size());
311  }
312  ada_clear_hash(getInner<ada_url>(inner));
313}
314 
315Url::SchemeType Url::getSchemeType() const {
316  uint8_t value = ada_get_scheme_type(getInner<ada_url>(inner));
317  KJ_REQUIRE(value <= static_cast<uint8_t>(SchemeType::FILE));
318  return static_cast<SchemeType>(value);
319}
320 
321Url::HostType Url::getHostType() const {
322  uint8_t value = ada_get_host_type(getInner<ada_url>(inner));
323  KJ_REQUIRE(value <= static_cast<uint8_t>(HostType::IPV6));
324  return static_cast<HostType>(value);
325}
326 
327Url Url::clone(EquivalenceOption option) const {
328  ada_url copy = ada_copy(getInner<ada_url>(inner));
329  if ((option & EquivalenceOption::IGNORE_FRAGMENTS) == EquivalenceOption::IGNORE_FRAGMENTS) {
330    ada_clear_hash(copy);
331  }
332  if ((option & EquivalenceOption::IGNORE_SEARCH) == EquivalenceOption::IGNORE_SEARCH) {
333    ada_clear_search(copy);
334  }
335  if ((option & EquivalenceOption::NORMALIZE_PATH) == EquivalenceOption::NORMALIZE_PATH) {
336    auto normalized = normalizePathEncoding(getPathname());
337    ada_set_pathname(copy, normalized.begin(), normalized.size());
338  }
339  return Url(wrap(copy));
340}
341 
342kj::Array<const char> Url::idnToUnicode(kj::ArrayPtr<const char> value) {
343  ada_owned_string result = ada_idna_to_unicode(value.begin(), value.size());
344  return kj::Array<const char>(result.data, result.length, AdaOwnedStringDisposer::INSTANCE);
345}
346 
347kj::Array<const char> Url::idnToAscii(kj::ArrayPtr<const char> value) {
348  ada_owned_string result = ada_idna_to_ascii(value.begin(), value.size());
349  return kj::Array<const char>(result.data, result.length, AdaOwnedStringDisposer::INSTANCE);
350}
351 
352kj::Maybe<Url> Url::tryResolve(kj::ArrayPtr<const char> input) const {
353  return tryParse(input, getHref());
354}
355 
356Url::Relative Url::getRelative(RelativeOption option) const {
357  if (option == RelativeOption::STRIP_TAILING_SLASHES) {
358    auto pathname = getPathname();
359    if (pathname.endsWith("/"_kj)) {
360      auto cloned = clone();
361      cloned.setPathname(pathname.first(pathname.size() - 1));
362      return cloned.getRelative();
363    }
364    // Otherwise, fall-through to the default behavior.
365  }
366  auto base = KJ_ASSERT_NONNULL(tryResolve("."_kj));
367  auto pos = KJ_ASSERT_NONNULL(getPathname().findLast('/'));
368  return {
369    .base = kj::mv(base),
370    .name = kj::str(getPathname().slice(pos + 1)),
371  };
372}
373 
374kj::Maybe<jsg::Url> Url::getParent() const {
375  auto parent = KJ_ASSERT_NONNULL(tryResolve("."_kj));
376  auto pathname = parent.getPathname();
377  if (pathname.size() == 1) return kj::none;
378  auto trimmed = kj::str(pathname.first(pathname.size() - 1));
379  parent.setPathname(trimmed);
380  return kj::mv(parent);
381}
382 
383kj::uint Url::hashCode() const {
384  return kj::hashCode(getHref());
385}
386 
387kj::Array<kj::byte> Url::percentDecode(kj::ArrayPtr<const kj::byte> input) {
388  std::string_view data(input.asChars().begin(), input.size());
389  auto str = ada::unicode::percent_decode(data, 0);
390  auto ret = kj::heapArray<kj::byte>(str.size());
391  memcpy(ret.begin(), str.data(), str.size());
392  return kj::mv(ret);
393}
394 
395// ======================================================================================
396 
397namespace {
398kj::Own<void> emptySearchParams() {
399  ada_url_search_params result = ada_parse_search_params(nullptr, 0);
400  KJ_ASSERT(result);
401  return kj::disposeWith<ada_free_search_params>(result);
402}
403}  // namespace
404 
405UrlSearchParams::UrlSearchParams(): inner(emptySearchParams()) {}
406 
407UrlSearchParams::UrlSearchParams(kj::Own<void> inner): inner(kj::mv(inner)) {}
408 
409bool UrlSearchParams::operator==(const UrlSearchParams& other) const {
410  return toStr() == other.toStr();
411}
412 
413void UrlSearchParams::reset(kj::Maybe<kj::ArrayPtr<const char>> input) {
414  KJ_IF_SOME(i, input) {
415    ada_search_params_reset(inner, i.begin(), i.size());
416  } else {
417    ada_search_params_reset(inner, nullptr, 0);
418  }
419}
420 
421kj::Maybe<UrlSearchParams> UrlSearchParams::tryParse(kj::ArrayPtr<const char> input) {
422  ada_url_search_params result = ada_parse_search_params(input.begin(), input.size());
423  if (!result) return kj::none;
424  return UrlSearchParams(kj::disposeWith<ada_free_search_params>(result));
425}
426 
427size_t UrlSearchParams::size() const {
428  return ada_search_params_size(getInner<ada_url_search_params>(inner));
429}
430 
431void UrlSearchParams::append(kj::ArrayPtr<const char> key, kj::ArrayPtr<const char> value) {
432  ada_search_params_append(
433      getInner<ada_url_search_params>(inner), key.begin(), key.size(), value.begin(), value.size());
434}
435 
436void UrlSearchParams::set(kj::ArrayPtr<const char> key, kj::ArrayPtr<const char> value) {
437  ada_search_params_set(
438      getInner<ada_url_search_params>(inner), key.begin(), key.size(), value.begin(), value.size());
439}
440 
441void UrlSearchParams::delete_(
442    kj::ArrayPtr<const char> key, kj::Maybe<kj::ArrayPtr<const char>> maybeValue) {
443  KJ_IF_SOME(value, maybeValue) {
444    ada_search_params_remove_value(getInner<ada_url_search_params>(inner), key.begin(), key.size(),
445        value.begin(), value.size());
446  } else {
447    ada_search_params_remove(getInner<ada_url_search_params>(inner), key.begin(), key.size());
448  }
449}
450 
451bool UrlSearchParams::has(
452    kj::ArrayPtr<const char> key, kj::Maybe<kj::ArrayPtr<const char>> maybeValue) const {
453  KJ_IF_SOME(value, maybeValue) {
454    return ada_search_params_has_value(getInner<ada_url_search_params>(inner), key.begin(),
455        key.size(), value.begin(), value.size());
456  } else {
457    return ada_search_params_has(getInner<ada_url_search_params>(inner), key.begin(), key.size());
458  }
459}
460 
461kj::Maybe<kj::ArrayPtr<const char>> UrlSearchParams::get(kj::ArrayPtr<const char> key) const {
462  auto result =
463      ada_search_params_get(getInner<ada_url_search_params>(inner), key.begin(), key.size());
464  if (result.data == nullptr) return kj::none;
465  return kj::ArrayPtr<const char>(result.data, result.length);
466}
467 
468kj::Array<kj::ArrayPtr<const char>> UrlSearchParams::getAll(kj::ArrayPtr<const char> key) const {
469  ada_strings results =
470      ada_search_params_get_all(getInner<ada_url_search_params>(inner), key.begin(), key.size());
471  size_t size = ada_strings_size(results);
472  kj::Vector<kj::ArrayPtr<const char>> items(size);
473  for (size_t n = 0; n < size; n++) {
474    auto item = ada_strings_get(results, n);
475    items.add(kj::ArrayPtr<const char>(item.data, item.length));
476  }
477  return items.releaseAsArray().attach(kj::defer([results]() { ada_free_strings(results); }));
478}
479 
480void UrlSearchParams::sort() {
481  ada_search_params_sort(getInner<ada_url_search_params>(inner));
482}
483 
484UrlSearchParams::KeyIterator UrlSearchParams::getKeys() const {
485  return KeyIterator(kj::disposeWith<ada_free_search_params_keys_iter>(
486      ada_search_params_get_keys(getInner<ada_url_search_params>(inner))));
487}
488 
489UrlSearchParams::ValueIterator UrlSearchParams::getValues() const {
490  return ValueIterator(kj::disposeWith<ada_free_search_params_values_iter>(
491      ada_search_params_get_values(getInner<ada_url_search_params>(inner))));
492}
493 
494UrlSearchParams::EntryIterator UrlSearchParams::getEntries() const {
495  return EntryIterator(kj::disposeWith<ada_free_search_params_entries_iter>(
496      ada_search_params_get_entries(getInner<ada_url_search_params>(inner))));
497}
498 
499kj::Array<const char> UrlSearchParams::toStr() const {
500  ada_owned_string result = ada_search_params_to_string(getInner<ada_url_search_params>(inner));
501  return kj::Array<const char>(result.data, result.length, AdaOwnedStringDisposer::INSTANCE);
502}
503 
504UrlSearchParams::KeyIterator::KeyIterator(kj::Own<void> inner): inner(kj::mv(inner)) {}
505 
506bool UrlSearchParams::KeyIterator::hasNext() const {
507  return ada_search_params_keys_iter_has_next(getInner<ada_url_search_params_keys_iter>(inner));
508}
509 
510kj::Maybe<kj::ArrayPtr<const char>> UrlSearchParams::KeyIterator::next() const {
511  if (!hasNext()) return kj::none;
512  auto next = ada_search_params_keys_iter_next(getInner<ada_url_search_params_keys_iter>(inner));
513  return kj::ArrayPtr<const char>(next.data, next.length);
514}
515 
516UrlSearchParams::ValueIterator::ValueIterator(kj::Own<void> inner): inner(kj::mv(inner)) {}
517 
518bool UrlSearchParams::ValueIterator::hasNext() const {
519  return ada_search_params_values_iter_has_next(getInner<ada_url_search_params_values_iter>(inner));
520}
521 
522kj::Maybe<kj::ArrayPtr<const char>> UrlSearchParams::ValueIterator::next() const {
523  if (!hasNext()) return kj::none;
524  auto next =
525      ada_search_params_values_iter_next(getInner<ada_url_search_params_values_iter>(inner));
526  return kj::ArrayPtr<const char>(next.data, next.length);
527}
528 
529UrlSearchParams::EntryIterator::EntryIterator(kj::Own<void> inner): inner(kj::mv(inner)) {}
530 
531bool UrlSearchParams::EntryIterator::hasNext() const {
532  return ada_search_params_entries_iter_has_next(
533      getInner<ada_url_search_params_entries_iter>(inner));
534}
535 
536kj::Maybe<UrlSearchParams::EntryIterator::Entry> UrlSearchParams::EntryIterator::next() const {
537  if (!hasNext()) return kj::none;
538  auto next =
539      ada_search_params_entries_iter_next(getInner<ada_url_search_params_entries_iter>(inner));
540  return Entry{
541    .key = kj::ArrayPtr<const char>(next.key.data, next.key.length),
542    .value = kj::ArrayPtr<const char>(next.value.data, next.value.length),
543  };
544}
545 
546// ======================================================================================
547// UrlPattern
548 
549namespace {
550 
551constexpr auto MODIFIER_OPTIONAL = "?"_kjc;
552constexpr auto MODIFIER_ZERO_OR_MORE = "*"_kjc;
553constexpr auto MODIFIER_ONE_OR_MORE = "+"_kjc;
554 
555inline bool isAsciiDigit(char c) {
556  return c >= '0' && c <= '9';
557};
558 
559inline bool isAscii(char codepoint) {
560  return codepoint >= 0x00 && codepoint <= 0x7f;
561};
562 
563inline bool isForbiddenHostCodepoint(char c) {
564  return c == 0x00 || c == 0x09 /* Tab */ || c == 0x0a /* LF */ || c == 0x0d /* CR */ || c == ' ' ||
565      c == '#' || c == '%' || c == '/' || c == ':' || c == '<' || c == '>' || c == '?' ||
566      c == '@' || c == '[' || c == '\\' || c == ']' || c == '^' || c == '|';
567};
568 
569// This is not meant to be a comprehensive validation that the hostname is
570// a proper IPv6 address. It's a quick check defined by the URLPattern spec.
571inline bool isIpv6(kj::ArrayPtr<const char> hostname) {
572  if (hostname.size() < 2) return false;
573  auto c1 = hostname[0];
574  auto c2 = hostname[1];
575  return (c1 == '[' || ((c1 == '{' || c1 == '\\') && c2 == '['));
576}
577 
578// This additional check deals with a known bug in the URLPattern spec. The URL parser will
579// allow (and generally ignore) invalid characters in the hostname when running with the
580// HOST state override. The URLPattern spec, however, assumes that it doesn't.
581inline bool isValidHostnameInput(kj::StringPtr input) {
582  return isIpv6(input) || std::none_of(input.begin(), input.end(), isForbiddenHostCodepoint);
583}
584 
585inline bool isValidCodepoint(uint32_t codepoint, bool first) {
586  // https://tc39.es/ecma262/#prod-IdentifierStart
587  if (first) {
588    return codepoint == '$' || codepoint == '_' || u_hasBinaryProperty(codepoint, UCHAR_ID_START);
589  }
590  return codepoint == '$' || codepoint == 0x200C ||  // Zero-width non-joiner
591      codepoint == 0x200D ||                         // Zero-width joiner
592      u_hasBinaryProperty(codepoint, UCHAR_ID_CONTINUE);
593};
594 
595inline kj::Maybe<kj::String> strFromMaybePtr(const kj::Maybe<kj::StringPtr>& ptr) {
596  return ptr.map([](const kj::StringPtr& ptr) { return kj::str(ptr); });
597}
598 
599using Canonicalizer = kj::Maybe<kj::String>(kj::StringPtr, kj::Maybe<kj::StringPtr>);
600 
601kj::Maybe<kj::String> canonicalizeProtocol(
602    kj::StringPtr protocol, kj::Maybe<kj::StringPtr> = kj::none) {
603  // @see https://wicg.github.io/urlpattern/#canonicalize-a-protocol
604  if (protocol.size() == 0) return kj::String();
605  auto input = kj::str(protocol, "://dummy.test");
606  KJ_IF_SOME(url, Url::tryParse(input.asPtr())) {
607    auto result = url.getProtocol();
608    return kj::str(result.first(result.size() - 1));
609  }
610  return kj::none;
611}
612 
613kj::Maybe<kj::String> canonicalizeUsername(
614    kj::StringPtr username, kj::Maybe<kj::StringPtr> = kj::none) {
615  // @see https://wicg.github.io/urlpattern/#canonicalize-a-username
616  if (username.size() == 0) return kj::String();
617  auto url = KJ_ASSERT_NONNULL(Url::tryParse("fake://dummy.test"_kj));
618  if (!url.setUsername(username)) return kj::none;
619  return kj::str(url.getUsername());
620}
621 
622kj::Maybe<kj::String> canonicalizePassword(
623    kj::StringPtr password, kj::Maybe<kj::StringPtr> = kj::none) {
624  // @see https://wicg.github.io/urlpattern/#canonicalize-a-password
625  if (password.size() == 0) return kj::String();
626  auto url = KJ_ASSERT_NONNULL(Url::tryParse("fake://dummy.test"_kj));
627  if (!url.setPassword(password)) return kj::none;
628  return kj::str(url.getPassword());
629}
630 
631kj::Maybe<kj::String> canonicalizeHostname(
632    kj::StringPtr hostname, kj::Maybe<kj::StringPtr> = kj::none) {
633  // @see https://wicg.github.io/urlpattern/#canonicalize-a-hostname
634  if (hostname.size() == 0) return kj::String();
635  auto url = KJ_ASSERT_NONNULL(Url::tryParse("fake://dummy.test"_kj));
636  if (!isValidHostnameInput(hostname)) return kj::none;
637  if (!url.setHostname(hostname)) return kj::none;
638  return kj::str(url.getHostname());
639}
640 
641kj::Maybe<kj::String> canonicalizeIpv6Hostname(
642    kj::StringPtr hostname, kj::Maybe<kj::StringPtr> = kj::none) {
643  // @see https://wicg.github.io/urlpattern/#canonicalize-an-ipv6-hostname
644  if (!std::all_of(hostname.begin(), hostname.end(),
645          [](char c) { return isHexDigit(c) || c == '[' || c == ']' || c == ':'; })) {
646    return kj::none;
647  }
648  return kj::str(hostname);
649}
650 
651kj::Maybe<kj::String> canonicalizePort(kj::StringPtr port, kj::Maybe<kj::StringPtr> protocol) {
652  // @see https://wicg.github.io/urlpattern/#canonicalize-a-port
653  if (port.size() == 0) return kj::String();
654  auto input = kj::str(protocol.orDefault("fake"_kj), "://dummy.test");
655  KJ_IF_SOME(url, Url::tryParse(input.asPtr())) {
656    if (!url.setPort(kj::Maybe(port))) return kj::none;
657    return kj::str(url.getPort());
658  }
659  return kj::none;
660}
661 
662kj::Maybe<kj::String> canonicalizePathname(
663    kj::StringPtr pathname, kj::Maybe<kj::StringPtr> = kj::none) {
664  // @see https://wicg.github.io/urlpattern/#canonicalize-a-pathname
665  if (pathname.size() == 0) return kj::String();
666  bool leadingSlash = pathname[0] == '/';
667  auto input = kj::str("fake://fake-url", leadingSlash ? "" : "/-", pathname);
668  KJ_IF_SOME(url, Url::tryParse(input.asPtr())) {
669    auto result = url.getPathname();
670    return leadingSlash ? kj::str(result) : kj::str(result.slice(2));
671  }
672  return kj::none;
673}
674 
675kj::Maybe<kj::String> canonicalizeOpaquePathname(
676    kj::StringPtr pathname, kj::Maybe<kj::StringPtr> = kj::none) {
677  // @see https://wicg.github.io/urlpattern/#canonicalize-an-opaque-pathname
678  if (pathname.size() == 0) return kj::String();
679  auto str = kj::str("fake:", pathname);
680  KJ_IF_SOME(url, Url::tryParse(str.asPtr())) {
681    return kj::str(url.getPathname());
682  }
683  return kj::none;
684}
685 
686kj::Maybe<kj::String> canonicalizeSearch(
687    kj::StringPtr search, kj::Maybe<kj::StringPtr> = kj::none) {
688  // @see https://wicg.github.io/urlpattern/#canonicalize-a-search
689  if (search.size() == 0) return kj::String();
690  auto url = KJ_ASSERT_NONNULL(Url::tryParse("fake://dummy.test"_kj));
691  url.setSearch(kj::Maybe(search));
692  return url.getSearch().size() > 0 ? kj::str(url.getSearch().slice(1)) : kj::String();
693}
694 
695kj::Maybe<kj::String> canonicalizeHash(kj::StringPtr hash, kj::Maybe<kj::StringPtr> = kj::none) {
696  // @see https://wicg.github.io/urlpattern/#canonicalize-a-hash
697  if (hash.size() == 0) return kj::String();
698  auto url = KJ_ASSERT_NONNULL(Url::tryParse("fake://dummy.test"_kj));
699  url.setHash(kj::Maybe(hash));
700  return url.getHash().size() > 0 ? kj::str(url.getHash().slice(1)) : kj::String();
701}
702 
703kj::Maybe<kj::String> chooseStr(kj::Maybe<kj::String> str, kj::Maybe<kj::StringPtr> other) {
704  KJ_IF_SOME(s, str) {
705    return kj::mv(s);
706  } else {
707    return strFromMaybePtr(other);
708  }
709}
710 
711kj::String stripSuffixFromProtocol(kj::ArrayPtr<const char> data) {
712  if (data.back() == ':') {
713    return kj::str(data.first(data.size() - 1));
714  }
715  return kj::str(data);
716}
717 
718kj::String escape(kj::ArrayPtr<const char> str, auto predicate) {
719  // Best case we don't have to escape anything so size remains the same,
720  // but let's pad a little just in case.
721  kj::Vector<char> result(str.size() + 10);
722  auto it = str.begin();
723  while (it != str.end()) {
724    auto c = *it;
725    if (predicate(c)) result.add('\\');
726    result.add(c);
727    ++it;
728  }
729  result.add('\0');
730  return kj::String(result.releaseAsArray());
731}
732 
733kj::String escapeRegexString(kj::ArrayPtr<const char> str) {
734  return escape(str, [](auto c) {
735    return c == '.' || c == '+' || c == '*' || c == '?' || c == '^' || c == '$' || c == '{' ||
736        c == '}' || c == '(' || c == ')' || c == '[' || c == ']' || c == '|' || c == '/' ||
737        c == '\\';
738  });
739}
740 
741kj::String escapePatternString(kj::ArrayPtr<const char> str) {
742  return escape(str, [](auto c) {
743    return c == '+' || c == '*' || c == '?' || c == ':' || c == '{' || c == '}' || c == '(' ||
744        c == ')' || c == '\\';
745  });
746}
747 
748struct CompileComponentOptions {
749  kj::Maybe<char> delimiter;
750  kj::Maybe<char> prefix;
751  kj::String segmentWildcardRegexp;
752 
753  kj::String initSegmentWildcardRegexp() {
754    KJ_IF_SOME(c, delimiter) {
755      return kj::str("[^\\", c, "]+");
756    } else {
757      return kj::str("[^]+");
758    }
759  }
760 
761  CompileComponentOptions(kj::Maybe<char> delimiter, kj::Maybe<char> prefix)
762      : delimiter(delimiter),
763        prefix(prefix),
764        segmentWildcardRegexp(initSegmentWildcardRegexp()) {}
765 
766  static const CompileComponentOptions DEFAULT;
767  static const CompileComponentOptions HOSTNAME;
768  static const CompileComponentOptions PATHNAME;
769};
770const CompileComponentOptions CompileComponentOptions::DEFAULT(kj::none, kj::none);
771const CompileComponentOptions CompileComponentOptions::HOSTNAME('.', kj::none);
772const CompileComponentOptions CompileComponentOptions::PATHNAME('/', '/');
773 
774// An individual piece of a URLPattern string. Used while parsing a URLPattern
775// string for the URLPattern constructor, test, or exec call.
776struct Part {
777  enum class Type {
778    FIXED_TEXT,
779    REGEXP,
780    SEGMENT_WILDCARD,
781    FULL_WILDCARD,
782  };
783 
784  enum class Modifier {
785    NONE,
786    OPTIONAL,      // ?
787    ZERO_OR_MORE,  // *
788    ONE_OR_MORE,   // +
789  };
790 
791  Type type;
792  Modifier modifier;
793  kj::String value;
794  kj::String name;
795  kj::Maybe<kj::String> prefix;
796  kj::Maybe<kj::String> suffix;
797};
798 
799kj::Maybe<kj::StringPtr> modifierToString(const Part::Modifier& modifier) {
800  switch (modifier) {
801    case Part::Modifier::NONE:
802      return kj::none;
803    case Part::Modifier::OPTIONAL:
804      return MODIFIER_OPTIONAL;
805    case Part::Modifier::ZERO_OR_MORE:
806      return MODIFIER_ZERO_OR_MORE;
807    case Part::Modifier::ONE_OR_MORE:
808      return MODIFIER_ONE_OR_MORE;
809  }
810  KJ_UNREACHABLE;
811}
812 
813// String inputs passed into URLPattern constructor are parsed by first
814// interpreting them into a list of Tokens. Each token has a type, a
815// position index in the input string, and a value. The value is either
816// a individual codepoint or a substring of input. Once the tokens are
817// determined, the parsing algorithms convert those into a Part list.
818// The part list is then used to generate the internal JavaScript RegExps
819// that are used for the actual matching operation.
820struct Token {
821  // Per the URLPattern spec, the tokenizer runs in one of two modes:
822  // Strict and Lenient. In Strict mode, invalid characters and sequences
823  // detected by the tokenizer will cause a TypeError to be thrown.
824  // In lenient mode, the invalid codepoints and sequences are marked
825  // but no error is thrown. When parsing a string passed to the
826  // URLPattern constructor, lenient mode is used. When parsing the
827  // pattern string for an individual component, strict mode is used.
828  enum class Policy {
829    STRICT,
830    LENIENT,
831  };
832 
833  enum class Type {
834    INVALID_CHAR,    // 0
835    OPEN,            // 1
836    CLOSE,           // 2
837    REGEXP,          // 3
838    NAME,            // 4
839    CHAR,            // 5
840    ESCAPED_CHAR,    // 6
841    OTHER_MODIFIER,  // 7
842    ASTERISK,        // 8
843    END,             // 9
844  };
845 
846  Type type = Type::INVALID_CHAR;
847  size_t index = 0;
848  kj::OneOf<char, kj::ArrayPtr<const char>> value = static_cast<char>(0);
849  Part::Modifier modifier = Part::Modifier::NONE;
850 
851  operator kj::String() const {
852    KJ_SWITCH_ONEOF(value) {
853      KJ_CASE_ONEOF(codepoint, char) {
854        return kj::str(codepoint);
855      }
856      KJ_CASE_ONEOF(ptr, kj::ArrayPtr<const char>) {
857        return kj::str(ptr);
858      }
859    }
860    KJ_UNREACHABLE;
861  }
862 
863  bool operator==(const kj::String& other) const {
864    KJ_SWITCH_ONEOF(value) {
865      KJ_CASE_ONEOF(codepoint, char) {
866        return false;
867      }
868      KJ_CASE_ONEOF(string, kj::ArrayPtr<const char>) {
869        return other == string;
870      }
871    }
872    KJ_UNREACHABLE;
873  }
874 
875  bool operator==(char other) {
876    KJ_SWITCH_ONEOF(value) {
877      KJ_CASE_ONEOF(codepoint, char) {
878        return codepoint == other;
879      }
880      KJ_CASE_ONEOF(string, kj::ArrayPtr<const char>) {
881        return false;
882      }
883    }
884    KJ_UNREACHABLE;
885  }
886 
887  static Token asterisk(size_t index) {
888    return {
889      .type = Type::ASTERISK,
890      .index = index,
891      .value = '*',
892      .modifier = Part::Modifier::ZERO_OR_MORE,
893    };
894  }
895 
896  static Token char_(size_t index, char codepoint) {
897    return {
898      .type = Type::CHAR,
899      .index = index,
900      .value = codepoint,
901    };
902  }
903 
904  static Token close(size_t index) {
905    return {
906      .type = Type::CLOSE,
907      .index = index,
908    };
909  }
910 
911  static Token end(size_t index) {
912    return {
913      .type = Type::END,
914      .index = index,
915    };
916  }
917 
918  static Token escapedChar(size_t index, char codepoint) {
919    return {
920      .type = Type::ESCAPED_CHAR,
921      .index = index,
922      .value = codepoint,
923    };
924  }
925 
926  static Token invalidChar(size_t index, char codepoint) {
927    return {
928      .index = index,
929      .value = codepoint,
930    };
931  }
932 
933  static Token invalidSegment(size_t index, kj::ArrayPtr<const char> segment) {
934    return {
935      .type = Type::INVALID_CHAR,
936      .index = index,
937      .value = segment,
938    };
939  }
940 
941  static Token name(size_t index, kj::ArrayPtr<const char> name) {
942    return {
943      .type = Type::NAME,
944      .index = index,
945      .value = name,
946    };
947  }
948 
949  static Token open(size_t index) {
950    return {
951      .type = Type::OPEN,
952      .index = index,
953    };
954  }
955 
956  static Token otherModifier(size_t index, char codepoint) {
957    KJ_DASSERT(codepoint == '?' || codepoint == '+');
958    return {
959      .type = Type::OTHER_MODIFIER,
960      .index = index,
961      .value = codepoint,
962      .modifier = codepoint == '?' ? Part::Modifier::OPTIONAL : Part::Modifier::ONE_OR_MORE,
963    };
964  }
965 
966  static Token regex(size_t index, kj::ArrayPtr<const char> regex) {
967    return {
968      .type = Type::REGEXP,
969      .index = index,
970      .value = regex,
971    };
972  }
973};
974 
975struct RegexAndNameList {
976  kj::String regex;
977  kj::Array<kj::String> names;
978};
979 
980UrlPattern::Result<kj::Array<Token>> tokenize(kj::StringPtr input, Token::Policy policy) {
981  auto it = input.begin();
982  size_t pos = 0;
983  kj::Vector<Token> tokenList(input.size() + 1);
984  // Scan the input and advance both it and pos until the given predicate return false.
985  const auto scanCodepoints = [&](auto predicate) {
986    bool first = true;
987    while (it != input.end()) {
988      uint32_t codepoint;
989      size_t starting = pos;
990      // Reads to the next codepoint boundary, incrementing pos accordingly.
991      // We use U8_NEXT_OR_FFFD here because the input is a raw sequence of
992      // UTF8 bytes but the predicate needs to check the decoded codepoint
993      // rather than looking at individual bytes. The macro will advance pos
994      // at is scans.
995      U8_NEXT_OR_FFFD(input.begin(), pos, input.size(), codepoint);
996      KJ_DASSERT(pos <= input.size());
997      // If our read codepoint does not match the predicate, we do not want to
998      // advance and we stop scanning.
999      if (!predicate(codepoint, first)) {
1000        pos = starting;
1001        break;
1002      }
1003      it += pos - starting;
1004      first = false;
1005    }
1006  };
1007 
1008  while (it != input.end()) {
1009    auto c = *it;
1010    switch (c) {
1011      case '*': {
1012        tokenList.add(Token::asterisk(pos++));
1013        break;
1014      }
1015      case '?': {
1016        KJ_FALLTHROUGH;
1017      }
1018      case '+': {
1019        tokenList.add(Token::otherModifier(pos++, c));
1020        break;
1021      }
1022      case '\\': {
1023        ++it;
1024        // The escape character is invalid if it comes at the end!
1025        if (it == input.end()) {
1026          if (policy == Token::Policy::STRICT) {
1027            return kj::str("Syntax error in URL Pattern: invalid escape character at ", pos);
1028          }
1029          tokenList.add(Token::invalidChar(pos++, c));
1030        } else {
1031          tokenList.add(Token::escapedChar(pos, *it));
1032          pos += 2;
1033        }
1034        break;
1035      }
1036      case '{': {
1037        tokenList.add(Token::open(pos++));
1038        break;
1039      }
1040      case '}': {
1041        tokenList.add(Token::close(pos++));
1042        break;
1043      }
1044      case ':': {
1045        ++it;
1046        // The name token is invalid if it comes at the end!
1047        if (it == input.end()) {
1048          if (policy == Token::Policy::STRICT) {
1049            return kj::str("Syntax error in URL Pattern: invalid name start at ", pos);
1050          }
1051          tokenList.add(Token::invalidChar(pos++, c));
1052          break;
1053        }
1054        auto start = ++pos;
1055        scanCodepoints(isValidCodepoint);
1056        if (start == pos) {
1057          // There was a name token suffix without a valid name! Oh, the inhumanity of it all.
1058          if (policy == Token::Policy::STRICT) {
1059            return kj::str("Syntax error in URL Pattern: invalid name start at ", pos - 1);
1060          }
1061          tokenList.add(Token::invalidChar(pos - 1, c));
1062        } else {
1063          if (it == input.end()) {
1064            tokenList.add(Token::name(start - 1, input.slice(start)));
1065          } else {
1066            tokenList.add(Token::name(start - 1, input.slice(start, pos)));
1067          }
1068        }
1069        // We purposefully do not increment the iterator here because we are
1070        // already at the next position.
1071 
1072        continue;
1073      }
1074      case '(': {
1075        ++it;
1076        // The group token is invalid if it comes at the end!
1077        if (it == input.end()) {
1078          if (policy == Token::Policy::STRICT) {
1079            return kj::str("Syntax error in URL Pattern: invalid regex start at ", pos);
1080          }
1081          tokenList.add(Token::invalidChar(pos++, c));
1082          break;
1083        }
1084        size_t depth = 1;
1085        size_t start = ++pos;
1086        bool error = false;
1087        while (it != input.end()) {
1088          auto rc = *it;
1089          if (!isAscii(rc)) {
1090            if (policy == Token::Policy::STRICT) {
1091              return kj::str("Syntax error in URL Pattern: invalid regex character at ", pos);
1092            }
1093            tokenList.add(Token::invalidChar(pos, rc));
1094            error = true;
1095            break;
1096          } else if (pos == start && rc == '?') {
1097            if (policy == Token::Policy::STRICT) {
1098              return kj::str("Syntax error in URL Pattern: invalid regex character at ", pos);
1099            }
1100            tokenList.add(Token::invalidChar(pos, rc));
1101            error = true;
1102            break;
1103          } else if (rc == '\\') {
1104            it++;
1105            // The escape character is invalid if it comes at the end of input
1106            if (it == input.end()) {
1107              if (policy == Token::Policy::STRICT) {
1108                return kj::str(
1109                    "Syntax error in URL Pattern: invalid escape character in regex at ", pos);
1110              }
1111              tokenList.add(Token::invalidChar(pos, rc));
1112              error = true;
1113              break;
1114            }
1115            pos++;
1116            rc = *it;
1117            if (!isAscii(rc)) {
1118              if (policy == Token::Policy::STRICT) {
1119                return kj::str(
1120                    "Syntax error in URL Pattern: invalid escaped character in regex at ", pos);
1121              }
1122              tokenList.add(Token::invalidChar(pos, rc));
1123              error = true;
1124              break;
1125            }
1126            pos++;
1127            it++;
1128            continue;
1129          } else if (rc == ')') {
1130            depth--;
1131            if (depth == 0) {
1132              pos++;
1133              it++;
1134              break;
1135            }
1136          } else if (rc == '(') {
1137            depth++;
1138            it++;
1139            // The group open character is invalid if it comes at the end of input
1140            if (it == input.end()) {
1141              if (policy == Token::Policy::STRICT) {
1142                return kj::str("Syntax error in URL Pattern: invalid group in regex at ", pos);
1143              }
1144              tokenList.add(Token::invalidChar(pos, rc));
1145              error = true;
1146              break;
1147            }
1148            pos++;
1149            rc = *it;
1150            if (rc != '?') {
1151              if (policy == Token::Policy::STRICT) {
1152                return kj::str("Syntax error in URL Pattern: invalid group in regex at ", pos);
1153              }
1154              tokenList.add(Token::invalidChar(pos, rc));
1155              error = true;
1156              break;
1157            }
1158          }
1159          it++;
1160          pos++;
1161        }
1162        if (error) continue;
1163        if (depth > 0 || start == pos) {
1164          if (policy == Token::Policy::STRICT) {
1165            return kj::str("Syntax error in URL Pattern: invalid regex segment at ", start);
1166          }
1167          tokenList.add(Token::invalidSegment(start, input.slice(start, pos - 1)));
1168        } else {
1169          tokenList.add(Token::regex(start - 1, input.slice(start, pos - 1)));
1170        }
1171        // We purposefully do not increment the iterator here because we are
1172        // already at the next position.
1173        continue;
1174      }
1175      default: {
1176        tokenList.add(Token::char_(pos++, c));
1177        break;
1178      }
1179    }
1180    if (it == input.end()) break;
1181    ++it;
1182  }
1183 
1184  tokenList.add(Token::end(input.size()));
1185  return tokenList.releaseAsArray();
1186}
1187 
1188UrlPattern::Result<kj::Array<Part>> parsePattern(
1189    kj::StringPtr input, Canonicalizer canonicalizer, const CompileComponentOptions& options) {
1190  kj::Array<Token> tokens = nullptr;
1191  KJ_SWITCH_ONEOF(tokenize(input, Token::Policy::STRICT)) {
1192    KJ_CASE_ONEOF(err, kj::String) {
1193      return kj::mv(err);
1194    }
1195    KJ_CASE_ONEOF(list, kj::Array<Token>) {
1196      tokens = kj::mv(list);
1197    }
1198  }
1199  // There should be at least one token in the list (the end token)
1200  KJ_DASSERT(tokens.size() > 0);
1201  kj::Vector<Part> partList(tokens.size());
1202  kj::Maybe<StringTreeHolder> pendingFixedValue;
1203  size_t index = 0;
1204  size_t nextNumericName = 0;
1205 
1206  auto segmentWildcardRegex = options.segmentWildcardRegexp.asPtr();
1207 
1208  auto appendToPendingFixedValue = [&](kj::StringPtr value) mutable {
1209    KJ_IF_SOME(pending, pendingFixedValue) {
1210      pending.append(value);
1211    } else {
1212      pendingFixedValue.emplace(kj::strTree(value));
1213    }
1214  };
1215 
1216  auto maybeAddPartFromPendingFixedValue = [&]() mutable -> bool {
1217    KJ_IF_SOME(fixedValue, pendingFixedValue) {
1218      kj::String value = kj::mv(fixedValue);
1219      pendingFixedValue = kj::none;
1220      if (value.size() == 0) return true;
1221      KJ_IF_SOME(canonical, canonicalizer(value, kj::none)) {
1222        partList.add(Part{
1223          .type = Part::Type::FIXED_TEXT,
1224          .modifier = Part::Modifier::NONE,
1225          .value = kj::mv(canonical),
1226        });
1227        return true;
1228      }
1229      return false;
1230    }
1231    return true;
1232  };
1233 
1234  auto tryConsumeToken = [&](Token::Type type) -> kj::Maybe<Token&> {
1235    KJ_DASSERT(index < tokens.size());
1236    auto& next = tokens[index];
1237    if (next.type != type) {
1238      return kj::none;
1239    }
1240    index++;
1241    return kj::Maybe<Token&>(next);
1242  };
1243 
1244  auto tryConsumeRegexOrWildcardToken = [&](kj::Maybe<Token&>& nameToken) {
1245    auto token = tryConsumeToken(Token::Type::REGEXP);
1246    if (nameToken == kj::none && token == kj::none) {
1247      token = tryConsumeToken(Token::Type::ASTERISK);
1248    }
1249    return token;
1250  };
1251 
1252  auto tryConsumeModifierToken = [&]() -> kj::Maybe<Token&> {
1253    KJ_IF_SOME(token, tryConsumeToken(Token::Type::OTHER_MODIFIER)) {
1254      return kj::Maybe<Token&>(token);
1255    }
1256    return tryConsumeToken(Token::Type::ASTERISK);
1257  };
1258 
1259  auto consumeText = [&]() mutable -> kj::String {
1260    StringTreeHolder result;
1261    while (true) {
1262      KJ_IF_SOME(token, tryConsumeToken(Token::Type::CHAR)) {
1263        result.append(kj::String(token));
1264      } else KJ_IF_SOME(token, tryConsumeToken(Token::Type::ESCAPED_CHAR)) {
1265        result.append(kj::String(token));
1266      } else {
1267        break;
1268      }
1269    }
1270    return kj::mv(result);
1271  };
1272 
1273  auto isDuplicateName = [&](kj::StringPtr name) -> bool {
1274    return std::any_of(
1275        partList.begin(), partList.end(), [&name](Part& part) { return part.name == name; });
1276  };
1277 
1278  auto maybeTokenToModifier = [](kj::Maybe<Token&> modifierToken) -> Part::Modifier {
1279    KJ_IF_SOME(token, modifierToken) {
1280      KJ_DASSERT(token.type == Token::Type::OTHER_MODIFIER || token.type == Token::Type::ASTERISK);
1281      return token.modifier;
1282    }
1283    return Part::Modifier::NONE;
1284  };
1285 
1286  auto addPart = [&](kj::Maybe<kj::String> maybePrefix, kj::Maybe<Token&> nameToken,
1287                     kj::Maybe<Token&> regexOrWildcardToken, kj::Maybe<kj::String> suffix,
1288                     kj::Maybe<Token&> modifierToken) mutable -> kj::Maybe<kj::String> {
1289    auto modifier = maybeTokenToModifier(modifierToken);
1290    if (nameToken == kj::none && regexOrWildcardToken == kj::none &&
1291        modifier == Part::Modifier::NONE) {
1292      KJ_IF_SOME(prefix, maybePrefix) {
1293        appendToPendingFixedValue(prefix);
1294      }
1295      return kj::none;
1296    }
1297    if (!maybeAddPartFromPendingFixedValue()) {
1298      return kj::str("Syntax error in URL Pattern");
1299    }
1300    if (nameToken == kj::none && regexOrWildcardToken == kj::none) {
1301      KJ_DASSERT(suffix == kj::none || KJ_ASSERT_NONNULL(suffix).size() == 0);
1302      KJ_IF_SOME(prefix, maybePrefix) {
1303        if (prefix.size() > 0) {
1304          KJ_IF_SOME(canonical, canonicalizer(prefix, kj::none)) {
1305            partList.add(Part{
1306              .type = Part::Type::FIXED_TEXT,
1307              .modifier = modifier,
1308              .value = kj::mv(canonical),
1309            });
1310          } else {
1311            return kj::str("Syntax error in URL Pattern");
1312          }
1313        }
1314      }
1315      return kj::none;
1316    }
1317    auto regexValue = kj::String();
1318    KJ_IF_SOME(token, regexOrWildcardToken) {
1319      if (token.type == Token::Type::ASTERISK) {
1320        regexValue = kj::str(".*");
1321      } else {
1322        regexValue = kj::String(token);
1323      }
1324    } else {
1325      regexValue = kj::str(segmentWildcardRegex);
1326    }
1327    auto type = Part::Type::REGEXP;
1328    if (regexValue == segmentWildcardRegex) {
1329      type = Part::Type::SEGMENT_WILDCARD;
1330      regexValue = kj::String();
1331    } else if (regexValue == ".*") {
1332      type = Part::Type::FULL_WILDCARD;
1333      regexValue = kj::String();
1334    }
1335    auto name = kj::String();
1336    KJ_IF_SOME(token, nameToken) {
1337      name = kj::String(token);
1338    } else if (regexOrWildcardToken != kj::none) {
1339      name = kj::str(nextNumericName++);
1340    }
1341 
1342    if (isDuplicateName(name)) {
1343      return kj::str("Syntax error in URL Pattern: Duplicated part names [", name, "]");
1344    }
1345 
1346    kj::Maybe<kj::String> encodedPrefix;
1347    kj::Maybe<kj::String> encodedSuffix;
1348    KJ_IF_SOME(prefix, maybePrefix) {
1349      KJ_IF_SOME(canonical, canonicalizer(prefix, kj::none)) {
1350        encodedPrefix = kj::mv(canonical);
1351      } else {
1352        return kj::str("Syntax error in URL Pattern");
1353      }
1354    }
1355    KJ_IF_SOME(s, suffix) {
1356      KJ_IF_SOME(canonical, canonicalizer(s, kj::none)) {
1357        encodedSuffix = kj::mv(canonical);
1358      } else {
1359        return kj::str("Syntax error in URL Pattern");
1360      }
1361    }
1362 
1363    partList.add(Part{
1364      .type = type,
1365      .modifier = modifier,
1366      .value = kj::mv(regexValue),
1367      .name = kj::mv(name),
1368      .prefix = kj::mv(encodedPrefix),
1369      .suffix = kj::mv(encodedSuffix),
1370    });
1371 
1372    return kj::none;
1373  };
1374 
1375  while (index < tokens.size()) {
1376    kj::Maybe<Token&> charToken = tryConsumeToken(Token::Type::CHAR);
1377    kj::Maybe<Token&> nameToken = tryConsumeToken(Token::Type::NAME);
1378    auto regexOrWildcardToken = tryConsumeRegexOrWildcardToken(nameToken);
1379 
1380    if (nameToken != kj::none || regexOrWildcardToken != kj::none) {
1381      auto maybePrefix = charToken.map([](Token& token) { return kj::String(token); });
1382 
1383      KJ_IF_SOME(prefix, maybePrefix) {
1384        if (prefix.size() > 0) {
1385          KJ_IF_SOME(c, options.prefix) {
1386            kj::String s;
1387            if (prefix[0] != c) {
1388              appendToPendingFixedValue(prefix);
1389              maybePrefix = kj::none;
1390            }
1391          } else {
1392            // If prefix is not empty, and is not the prefixCodePoint
1393            // (which it can't be if we're here given that there is
1394            // no prefix char), when we append prefix to pendingFixedValue,
1395            // and clear prefix.
1396            appendToPendingFixedValue(prefix);
1397            maybePrefix = kj::none;
1398          }
1399        }
1400      }
1401      if (!maybeAddPartFromPendingFixedValue()) {
1402        return kj::str("Syntax error in URL Pattern");
1403      }
1404      auto modifierToken = tryConsumeModifierToken();
1405      KJ_IF_SOME(err,
1406          addPart(kj::mv(maybePrefix), nameToken, regexOrWildcardToken, kj::none, modifierToken)) {
1407        return kj::mv(err);
1408      }
1409      continue;
1410    }
1411 
1412    kj::Maybe<Token&> fixedToken = charToken;
1413    if (fixedToken == kj::none) {
1414      fixedToken = tryConsumeToken(Token::Type::ESCAPED_CHAR);
1415    }
1416    KJ_IF_SOME(token, fixedToken) {
1417      appendToPendingFixedValue(kj::String(token));
1418      continue;
1419    }
1420    if (tryConsumeToken(Token::Type::OPEN) != kj::none) {
1421      auto maybePrefix = consumeText();
1422      auto nameToken = tryConsumeToken(Token::Type::NAME);
1423      regexOrWildcardToken = tryConsumeRegexOrWildcardToken(nameToken);
1424      auto suffix = consumeText();
1425      if (tryConsumeToken(Token::Type::CLOSE) == kj::none) {
1426        return kj::str("Syntax error in URL Pattern: Missing required close token");
1427      }
1428      auto modifierToken = tryConsumeModifierToken();
1429      KJ_IF_SOME(err,
1430          addPart(kj::mv(maybePrefix), nameToken, regexOrWildcardToken, kj::mv(suffix),
1431              modifierToken)) {
1432        return kj::mv(err);
1433      }
1434      continue;
1435    }
1436    if (!maybeAddPartFromPendingFixedValue()) {
1437      return kj::str("Syntax error in URL Pattern");
1438    }
1439 
1440    if (tryConsumeToken(Token::Type::END) == kj::none) {
1441      return kj::str("Syntax error in URL Pattern: Missing required end token");
1442    }
1443  }
1444 
1445  return partList.releaseAsArray();
1446}
1447 
1448RegexAndNameList generateRegexAndNameList(
1449    kj::ArrayPtr<Part> partList, const CompileComponentOptions& options) {
1450  // Worst case is that the nameList is equal to partList, although that will almost never
1451  // be the case, so let's be more conservative in what we reserve.
1452  kj::Vector<kj::String> nameList(partList.size() / 2);
1453  StringTreeHolder regex("^"_kj);
1454 
1455  for (auto& part: partList) {
1456    if (part.type == Part::Type::FIXED_TEXT) {
1457      auto escaped = escapeRegexString(part.value);
1458      if (part.modifier == Part::Modifier::NONE) {
1459        regex.append(kj::mv(escaped));
1460      } else {
1461        regex.append("(?:", kj::mv(escaped), ")");
1462        KJ_IF_SOME(c, modifierToString(part.modifier)) {
1463          regex.append(c);
1464        }
1465      }
1466      continue;
1467    }
1468 
1469    KJ_DASSERT(part.name.size() > 0);
1470    nameList.add(kj::mv(part.name));
1471    auto value = part.type == Part::Type::SEGMENT_WILDCARD ? kj::str(options.segmentWildcardRegexp)
1472        : part.type == Part::Type::FULL_WILDCARD           ? kj::str(".*")
1473                                                           : kj::mv(part.value);
1474 
1475    if (part.prefix == kj::none && part.suffix == kj::none) {
1476      if (part.modifier == Part::Modifier::NONE || part.modifier == Part::Modifier::OPTIONAL) {
1477        regex.append("(", value, ")");
1478        KJ_IF_SOME(c, modifierToString(part.modifier)) {
1479          regex.append(c);
1480        }
1481      } else {
1482        regex.append("((?:", value, ")");
1483        KJ_IF_SOME(c, modifierToString(part.modifier)) {
1484          regex.append(c, ")");
1485        } else {
1486          regex.append(")");
1487        }
1488      }
1489      continue;
1490    }
1491 
1492    auto escapedPrefix = part.prefix.map([](kj::String& str) {
1493      return escapeRegexString(str);
1494    }).orDefault(kj::String());
1495    auto escapedSuffix = part.suffix.map([](kj::String& str) {
1496      return escapeRegexString(str);
1497    }).orDefault(kj::String());
1498 
1499    if (part.modifier == Part::Modifier::NONE || part.modifier == Part::Modifier::OPTIONAL) {
1500      regex.append("(?:", escapedPrefix, "(", value, ")", escapedSuffix, ")");
1501      KJ_IF_SOME(c, modifierToString(part.modifier)) {
1502        regex.append(c);
1503      }
1504      continue;
1505    }
1506 
1507    regex.append("(?:", escapedPrefix, "((?:", value, ")(?:", escapedSuffix, escapedPrefix,
1508        "(?:", value, "))*)", escapedSuffix, ")");
1509    if (part.modifier == Part::Modifier::ZERO_OR_MORE) {
1510      regex.append(MODIFIER_ZERO_OR_MORE);
1511    }
1512  }
1513 
1514  regex.append("$");
1515 
1516  return RegexAndNameList{
1517    .regex = kj::mv(regex),
1518    .names = nameList.releaseAsArray(),
1519  };
1520}
1521 
1522kj::String generatePatternString(
1523    kj::ArrayPtr<Part> partList, const CompileComponentOptions& options) {
1524  StringTreeHolder pattern;
1525  Part* previousPart = nullptr;
1526  Part* nextPart = nullptr;
1527  bool customName = false;
1528  bool needsGrouping = false;
1529  bool prefixIsEmpty = false;
1530 
1531  const auto partPrefixEmpty = [](Part* part) {
1532    if (part == nullptr) return true;
1533    KJ_IF_SOME(prefix, part->prefix) {
1534      return prefix.size() == 0;
1535    }
1536    return true;
1537  };
1538 
1539  const auto partSuffixEmpty = [](Part* part) {
1540    if (part == nullptr) return true;
1541    KJ_IF_SOME(prefix, part->suffix) {
1542      return prefix.size() == 0;
1543    }
1544    return true;
1545  };
1546 
1547  const auto partSuffixIsValid = [&](Part* part) {
1548    if (partSuffixEmpty(part)) return false;
1549    auto& suffix = KJ_ASSERT_NONNULL(part->suffix);
1550    return isValidCodepoint(suffix[0], false);
1551  };
1552 
1553  const auto checkNeedsGrouping = [&](Part& part) {
1554    KJ_IF_SOME(suffix, part.suffix) {
1555      if (suffix.size() > 0) return true;
1556    }
1557    KJ_IF_SOME(prefix, part.prefix) {
1558      if (prefix.size() > 0) {
1559        KJ_IF_SOME(c, options.prefix) {
1560          return prefix[0] != c;
1561        }
1562      }
1563    }
1564    if (!needsGrouping && prefixIsEmpty && customName &&
1565        part.type == Part::Type::SEGMENT_WILDCARD && part.modifier == Part::Modifier::NONE &&
1566        nextPart != nullptr && partPrefixEmpty(nextPart) && partSuffixEmpty(nextPart)) {
1567      if (nextPart->type == Part::Type::FIXED_TEXT) {
1568        return nextPart->name.size() > 0 && isValidCodepoint(nextPart->name[0], false);
1569      } else {
1570        return nextPart->name.size() > 0 && isAsciiDigit(nextPart->name[0]);
1571      }
1572    }
1573    return false;
1574  };
1575 
1576  for (size_t n = 0; n < partList.size(); n++) {
1577    auto& part = partList[n];
1578    previousPart = nullptr;
1579    nextPart = nullptr;
1580    if (n > 0) previousPart = &partList[n - 1];
1581    if (n < partList.size() - 1) nextPart = &partList[n + 1];
1582 
1583    if (part.type == Part::Type::FIXED_TEXT) {
1584      if (part.modifier == Part::Modifier::NONE) {
1585        pattern.append(escapePatternString(part.value));
1586        continue;
1587      }
1588      pattern.append("{", escapePatternString(part.value), "}");
1589      KJ_IF_SOME(c, modifierToString(part.modifier)) {
1590        pattern.append(c);
1591      }
1592      continue;
1593    }
1594 
1595    KJ_DASSERT(part.name.size() > 0);
1596    customName = !isAsciiDigit(part.name[0]);
1597    prefixIsEmpty = partPrefixEmpty(&part);
1598    needsGrouping = checkNeedsGrouping(part);
1599 
1600    if (!needsGrouping && prefixIsEmpty && previousPart != nullptr) {
1601      // These additional checks on previousPart have to be separated out from the outer
1602      // if because in some cases, they may be evaluated before the previousPart != nullptr
1603      // check.
1604      if (previousPart->type == Part::Type::FIXED_TEXT &&
1605          (previousPart->value.size() > 0 &&
1606              previousPart->value[previousPart->value.size() - 1] == options.prefix.orDefault(0))) {
1607        needsGrouping = true;
1608      }
1609    }
1610 
1611    StringTreeHolder subPattern;
1612    KJ_IF_SOME(prefix, part.prefix) {
1613      subPattern.append(escapePatternString(prefix));
1614    }
1615    if (customName) {
1616      subPattern.append(":", part.name);
1617    }
1618 
1619    if (part.type == Part::Type::REGEXP) {
1620      subPattern.append("(", part.value, ")");
1621    } else if (part.type == Part::Type::SEGMENT_WILDCARD && !customName) {
1622      subPattern.append("(", options.segmentWildcardRegexp, ")");
1623    } else if (part.type == Part::Type::FULL_WILDCARD) {
1624      if (!customName &&
1625          (previousPart == nullptr || previousPart->type == Part::Type::FIXED_TEXT ||
1626              previousPart->modifier != Part::Modifier::NONE || needsGrouping || !prefixIsEmpty)) {
1627        subPattern.append(MODIFIER_ZERO_OR_MORE);
1628      } else {
1629        subPattern.append("(.*)");
1630      }
1631    }
1632    if (part.type == Part::Type::SEGMENT_WILDCARD && customName && partSuffixIsValid(&part)) {
1633      subPattern.append("\\");
1634    }
1635 
1636    KJ_IF_SOME(suffix, part.suffix) {
1637      subPattern.append(escapePatternString(suffix));
1638    }
1639 
1640    if (needsGrouping) {
1641      kj::String sub = kj::mv(subPattern);
1642      subPattern = kj::strTree("{", kj::mv(sub), "}");
1643    }
1644 
1645    KJ_IF_SOME(c, modifierToString(part.modifier)) {
1646      subPattern.append(c);
1647    }
1648 
1649    kj::String sub = kj::mv(subPattern);
1650    pattern.append(kj::mv(sub));
1651  }
1652  return kj::mv(pattern);
1653}
1654 
1655UrlPattern::Result<UrlPattern::Component> tryCompileComponent(kj::Maybe<kj::String>& input,
1656    Canonicalizer canonicalizer,
1657    const CompileComponentOptions& options) {
1658  auto pattern = kj::mv(input).orDefault([] { return kj::str(MODIFIER_ZERO_OR_MORE); });
1659  KJ_SWITCH_ONEOF(parsePattern(pattern, canonicalizer, options)) {
1660    KJ_CASE_ONEOF(err, kj::String) {
1661      return kj::mv(err);
1662    }
1663    KJ_CASE_ONEOF(partList, kj::Array<Part>) {
1664      auto pattern = generatePatternString(partList, options);
1665      auto regexAndNameList = generateRegexAndNameList(partList, options);
1666      return UrlPattern::Component(
1667          kj::mv(pattern), kj::mv(regexAndNameList.regex), kj::mv(regexAndNameList.names));
1668    }
1669  }
1670  KJ_UNREACHABLE;
1671}
1672 
1673bool protocolComponentMatchesSpecialScheme(
1674    kj::StringPtr regex, const UrlPattern::CompileOptions& options) {
1675  std::regex rx(regex.begin(), regex.size());
1676  std::cmatch cmatch;
1677  return std::regex_match("http", cmatch, rx) || std::regex_match("https", cmatch, rx) ||
1678      std::regex_match("ws", cmatch, rx) || std::regex_match("wss", cmatch, rx) ||
1679      std::regex_match("ftp", cmatch, rx);
1680}
1681 
1682UrlPattern::Result<UrlPattern::Init> tryParseConstructorString(
1683    kj::StringPtr input, const UrlPattern::CompileOptions& options) {
1684  enum class State {
1685    INIT,
1686    PROTOCOL,
1687    AUTHORITY,
1688    USERNAME,
1689    PASSWORD,
1690    HOSTNAME,
1691    PORT,
1692    PATHNAME,
1693    SEARCH,
1694    HASH,
1695    DONE,
1696  };
1697  State state = State::INIT;
1698 
1699  size_t inc = 0;
1700  size_t depth = 0;
1701  size_t ipv6Depth = 0;
1702  bool protocolMatchesSpecialScheme = false;
1703 
1704  UrlPattern::Init result{
1705    .baseUrl = strFromMaybePtr(options.baseUrl),
1706  };
1707 
1708  kj::Array<Token> tokens = nullptr;
1709  KJ_SWITCH_ONEOF(tokenize(input, Token::Policy::LENIENT)) {
1710    KJ_CASE_ONEOF(err, kj::String) {
1711      return kj::mv(err);
1712    }
1713    KJ_CASE_ONEOF(list, kj::Array<Token>) {
1714      tokens = kj::mv(list);
1715    }
1716  }
1717 
1718  // There should always be at least one token, and it should be type end.
1719  KJ_DASSERT(tokens.size() > 0);
1720  KJ_DASSERT(tokens.back().type == Token::Type::END);
1721  auto it = tokens.begin();
1722  auto start = it;
1723 
1724  const auto rewind = [&](kj::Maybe<State> maybeNewState = kj::none) {
1725    KJ_DASSERT(start <= it);
1726    it = start;
1727    KJ_DASSERT(tokens.begin() <= it && it < tokens.end());
1728    inc = 0;
1729    KJ_IF_SOME(newState, maybeNewState) {
1730      state = newState;
1731    }
1732  };
1733 
1734  const auto makeComponentString = [&]() {
1735    KJ_DASSERT(tokens.begin() <= it && it < tokens.end());
1736    KJ_DASSERT(start->index <= it->index);
1737    return kj::str(input.slice(start->index, it->index));
1738  };
1739 
1740  const auto changeState = [&](State newState, int skip) {
1741    if (state != State::INIT && state != State::AUTHORITY && state != State::DONE) {
1742      auto value = makeComponentString();
1743      switch (state) {
1744        case State::PROTOCOL: {
1745          result.protocol = kj::mv(value);
1746          break;
1747        }
1748        case State::USERNAME: {
1749          result.username = kj::mv(value);
1750          break;
1751        }
1752        case State::PASSWORD: {
1753          result.password = kj::mv(value);
1754          break;
1755        }
1756        case State::HOSTNAME: {
1757          result.hostname = kj::mv(value);
1758          break;
1759        }
1760        case State::PORT: {
1761          result.port = kj::mv(value);
1762          break;
1763        }
1764        case State::PATHNAME: {
1765          result.pathname = kj::mv(value);
1766          break;
1767        }
1768        case State::SEARCH: {
1769          result.search = kj::mv(value);
1770          break;
1771        }
1772        case State::HASH: {
1773          result.hash = kj::mv(value);
1774          break;
1775        }
1776        case State::INIT: {
1777          KJ_FALLTHROUGH;
1778        }
1779        case State::AUTHORITY: {
1780          KJ_FALLTHROUGH;
1781        }
1782        case State::DONE: {
1783          KJ_UNREACHABLE;
1784        }
1785      }
1786    }
1787    state = newState;
1788    KJ_DASSERT(it + skip <= tokens.end());
1789    it += skip;
1790    KJ_DASSERT(tokens.begin() <= it && it < tokens.end());
1791    start = it;
1792    inc = 0;
1793  };
1794 
1795  const auto isNonSpecialPatternChar = [&](auto iter, char c) {
1796    KJ_DASSERT(tokens.begin() <= iter && iter < tokens.end());
1797    Token& token = *iter;
1798    return (token.type == Token::Type::CHAR || token.type == Token::Type::ESCAPED_CHAR ||
1799               token.type == Token::Type::INVALID_CHAR) &&
1800        token == c;
1801  };
1802 
1803  const auto isProtocolSuffix = [&]() { return isNonSpecialPatternChar(it, ':'); };
1804 
1805  const auto nextIsAuthoritySlashes = [&]() {
1806    return isNonSpecialPatternChar(it + 1, '/') && isNonSpecialPatternChar(it + 2, '/');
1807  };
1808 
1809  const auto isIdentityTerminator = [&]() { return isNonSpecialPatternChar(it, '@'); };
1810 
1811  const auto isPasswordPrefix = [&]() { return isNonSpecialPatternChar(it, ':'); };
1812 
1813  const auto isPortPrefix = [&]() { return isNonSpecialPatternChar(it, ':'); };
1814 
1815  const auto isPathnameStart = [&]() { return isNonSpecialPatternChar(it, '/'); };
1816 
1817  const auto isSearchPrefix = [&]() {
1818    if (isNonSpecialPatternChar(it, '?')) {
1819      return true;
1820    }
1821    auto& token = *it;
1822    if (token != '?') return false;
1823 
1824    if (it == tokens.begin()) return true;
1825 
1826    auto& previousToken = *(it - 1);
1827    return previousToken.type != Token::Type::NAME && previousToken.type != Token::Type::REGEXP &&
1828        previousToken.type != Token::Type::CLOSE && previousToken.type != Token::Type::ASTERISK;
1829  };
1830 
1831  const auto isHashPrefix = [&]() { return isNonSpecialPatternChar(it, '#'); };
1832 
1833  const auto isGroupOpen = [&]() { return it->type == Token::Type::OPEN; };
1834 
1835  const auto isGroupClose = [&]() { return it->type == Token::Type::CLOSE; };
1836 
1837  const auto isIPv6Open = [&]() { return isNonSpecialPatternChar(it, '['); };
1838 
1839  const auto isIPv6Close = [&]() { return isNonSpecialPatternChar(it, ']'); };
1840 
1841  const auto computeMatchesSpecialScheme = [&] {
1842    kj::Maybe<kj::String> input = makeComponentString();
1843    KJ_SWITCH_ONEOF(tryCompileComponent(
1844                        input, &canonicalizeProtocol, CompileComponentOptions::DEFAULT)) {
1845      KJ_CASE_ONEOF(err, kj::String) {
1846        // Ignore any errors at this point. If the component is invalid we'll
1847        // catch it later.
1848        return false;
1849      }
1850      KJ_CASE_ONEOF(component, UrlPattern::Component) {
1851        return protocolComponentMatchesSpecialScheme(component.getRegex(), options);
1852      }
1853    }
1854    KJ_UNREACHABLE;
1855  };
1856 
1857  while (it != tokens.end()) {
1858    Token& token = *it;
1859    inc = 1;
1860 
1861    if (token.type == Token::Type::END) {
1862      if (state == State::INIT) {
1863        rewind();
1864        if (isHashPrefix()) {
1865          changeState(State::HASH, 1);
1866        } else if (isSearchPrefix()) {
1867          changeState(State::SEARCH, 1);
1868          result.hash = kj::String();
1869        } else {
1870          changeState(State::PATHNAME, 0);
1871          result.search = kj::String();
1872          result.hash = kj::String();
1873        }
1874        // Since we called rewind and we know that sets inc to zero,
1875        // and we know that nothing else here changed inc, there's no
1876        // need to try to advance. Just continue.
1877        continue;
1878      }
1879      if (state == State::AUTHORITY) {
1880        rewind(State::HOSTNAME);
1881        // Since we called rewind and we know that sets inc to zero,
1882        // there's no need to try to advance. Just continue.
1883        continue;
1884      }
1885      // We hit the end and we're all done!
1886      changeState(State::DONE, 0);
1887      break;
1888    }
1889    if (isGroupOpen()) {
1890      depth++;
1891      it += inc;
1892      continue;
1893    }
1894    if (depth > 0) {
1895      if (isGroupClose()) {
1896        depth--;
1897      } else {
1898        it += inc;
1899        continue;
1900      }
1901    }
1902 
1903    switch (state) {
1904      case State::INIT: {
1905        if (isProtocolSuffix()) {
1906          result.username = kj::String();
1907          result.password = kj::String();
1908          result.hostname = kj::String();
1909          result.port = kj::String();
1910          result.pathname = kj::String();
1911          result.search = kj::String();
1912          result.hash = kj::String();
1913          rewind(State::PROTOCOL);
1914        }
1915        break;
1916      }
1917      case State::PROTOCOL: {
1918        if (isProtocolSuffix()) {
1919          computeMatchesSpecialScheme();
1920          if (protocolMatchesSpecialScheme) result.pathname = kj::str("/");
1921          if (nextIsAuthoritySlashes())
1922            changeState(State::AUTHORITY, 3);
1923          else if (protocolMatchesSpecialScheme)
1924            changeState(State::AUTHORITY, 1);
1925          else
1926            changeState(State::PATHNAME, 1);
1927        }
1928        break;
1929      }
1930      case State::AUTHORITY: {
1931        if (isIdentityTerminator())
1932          rewind(State::USERNAME);
1933        else if (isPathnameStart() || isSearchPrefix() || isHashPrefix())
1934          rewind(State::HOSTNAME);
1935        break;
1936      }
1937      case State::USERNAME: {
1938        if (isPasswordPrefix())
1939          changeState(State::PASSWORD, 1);
1940        else if (isIdentityTerminator())
1941          changeState(State::HOSTNAME, 1);
1942        break;
1943      }
1944      case State::PASSWORD: {
1945        if (isIdentityTerminator()) changeState(State::HOSTNAME, 1);
1946        break;
1947      }
1948      case State::HOSTNAME: {
1949        if (isIPv6Open())
1950          ipv6Depth++;
1951        else if (isIPv6Close())
1952          ipv6Depth--;
1953        else if (isPortPrefix() && ipv6Depth == 0)
1954          changeState(State::PORT, 1);
1955        else if (isPathnameStart())
1956          changeState(State::PATHNAME, 0);
1957        else if (isSearchPrefix())
1958          changeState(State::SEARCH, 1);
1959        else if (isHashPrefix())
1960          changeState(State::HASH, 1);
1961        break;
1962      }
1963      case State::PORT: {
1964        if (isPathnameStart())
1965          changeState(State::PATHNAME, 0);
1966        else if (isSearchPrefix())
1967          changeState(State::SEARCH, 1);
1968        else if (isHashPrefix())
1969          changeState(State::HASH, 1);
1970        break;
1971      }
1972      case State::PATHNAME: {
1973        if (isSearchPrefix())
1974          changeState(State::SEARCH, 1);
1975        else if (isHashPrefix())
1976          changeState(State::HASH, 1);
1977        break;
1978      }
1979      case State::SEARCH: {
1980        if (isHashPrefix()) changeState(State::HASH, 1);
1981        break;
1982      }
1983      case State::HASH: {
1984        // Nothing to do.
1985        break;
1986      }
1987      case State::DONE: {
1988        KJ_UNREACHABLE;
1989      }
1990    }
1991 
1992    it += inc;
1993  }
1994 
1995  if (result.protocol == kj::none && result.baseUrl == kj::none) {
1996    return kj::str("Syntax error in URL Pattern: a relative pattern must have a base URL.");
1997  }
1998 
1999  return kj::mv(result);
2000}
2001}  // namespace
2002 
2003UrlPattern::Component::Component(kj::String pattern, kj::String regex, kj::Array<kj::String> names)
2004    : pattern(kj::mv(pattern)),
2005      regex(kj::mv(regex)),
2006      names(kj::mv(names)) {}
2007 
2008UrlPattern::Result<UrlPattern> UrlPattern::tryCompileInit(
2009    UrlPattern::Init init, const UrlPattern::CompileOptions& options) {
2010  kj::Vector<UrlPattern::Component> components(7);
2011 
2012  bool matchesSpecialScheme = false;
2013 
2014  KJ_SWITCH_ONEOF(tryCompileComponent(
2015                      init.protocol, &canonicalizeProtocol, CompileComponentOptions::DEFAULT)) {
2016    KJ_CASE_ONEOF(err, kj::String) {
2017      return kj::mv(err);
2018    }
2019    KJ_CASE_ONEOF(component, UrlPattern::Component) {
2020      matchesSpecialScheme = protocolComponentMatchesSpecialScheme(component.getRegex(), options);
2021      components.add(kj::mv(component));
2022    }
2023  }
2024 
2025  const auto handleComponent =
2026      [&](auto& input, Canonicalizer canonicalizer,
2027          const CompileComponentOptions& options) -> kj::Maybe<kj::String> {
2028    KJ_SWITCH_ONEOF(tryCompileComponent(input, canonicalizer, options)) {
2029      KJ_CASE_ONEOF(err, kj::String) {
2030        return kj::mv(err);
2031      }
2032      KJ_CASE_ONEOF(component, UrlPattern::Component) {
2033        components.add(kj::mv(component));
2034        return kj::none;
2035      }
2036    }
2037    KJ_UNREACHABLE;
2038  };
2039 
2040  KJ_IF_SOME(err,
2041      handleComponent(init.username, &canonicalizeUsername, CompileComponentOptions::DEFAULT)) {
2042    return kj::mv(err);
2043  }
2044  KJ_IF_SOME(err,
2045      handleComponent(init.password, &canonicalizePassword, CompileComponentOptions::DEFAULT)) {
2046    return kj::mv(err);
2047  }
2048 
2049  Canonicalizer* hostnameCanonicalizer = &canonicalizeHostname;
2050  KJ_IF_SOME(hostname, init.hostname) {
2051    if (isIpv6(hostname.asPtr())) {
2052      hostnameCanonicalizer = &canonicalizeIpv6Hostname;
2053    }
2054  }
2055  KJ_IF_SOME(err,
2056      handleComponent(init.hostname, hostnameCanonicalizer, CompileComponentOptions::HOSTNAME)) {
2057    return kj::mv(err);
2058  }
2059 
2060  KJ_IF_SOME(err, handleComponent(init.port, &canonicalizePort, CompileComponentOptions::DEFAULT)) {
2061    return kj::mv(err);
2062  }
2063 
2064  KJ_IF_SOME(err,
2065      handleComponent(init.pathname,
2066          matchesSpecialScheme ? &canonicalizePathname : &canonicalizeOpaquePathname,
2067          matchesSpecialScheme ? CompileComponentOptions::PATHNAME
2068                               : CompileComponentOptions::DEFAULT)) {
2069    return kj::mv(err);
2070  }
2071  KJ_IF_SOME(err,
2072      handleComponent(init.search, &canonicalizeSearch, CompileComponentOptions::DEFAULT)) {
2073    return kj::mv(err);
2074  }
2075  KJ_IF_SOME(err, handleComponent(init.hash, &canonicalizeHash, CompileComponentOptions::DEFAULT)) {
2076    return kj::mv(err);
2077  }
2078  return UrlPattern(components.releaseAsArray(), options.ignoreCase);
2079}
2080 
2081UrlPattern::Result<UrlPattern::Init> UrlPattern::processInit(
2082    UrlPattern::Init init, kj::Maybe<UrlPattern::ProcessInitOptions> maybeOptions) {
2083  auto options = maybeOptions.orDefault({});
2084 
2085  Init result;
2086  kj::Maybe<Url> maybeBaseUrl;
2087 
2088  const auto isAbsolutePathname = [&](kj::StringPtr str) {
2089    if (str.size() == 0) return false;
2090    char c = str[0];
2091    if (c == '/') return true;
2092    if (options.mode == ProcessInitOptions::Mode::URL) return false;
2093    return str.size() > 1 && (c == '\\' || c == '{') && str[1] == '/';
2094  };
2095 
2096  KJ_IF_SOME(base, init.baseUrl) {
2097    KJ_IF_SOME(url, Url::tryParse(base.asPtr())) {
2098      result.protocol = stripSuffixFromProtocol(url.getProtocol());
2099      result.username = kj::str(url.getUsername());
2100      result.password = kj::str(url.getPassword());
2101      result.hostname = kj::str(url.getHostname());
2102      result.port = kj::str(url.getPort());
2103      result.pathname = escapePatternString(url.getPathname());
2104      if (url.getSearch().size() > 0) {
2105        result.search = escapePatternString(url.getSearch().slice(1));
2106      } else {
2107        result.search = kj::String();
2108      }
2109      if (url.getHash().size() > 0) {
2110        result.hash = escapePatternString(url.getHash().slice(1));
2111      } else {
2112        result.hash = kj::String();
2113      }
2114      result.baseUrl = kj::mv(base);
2115      maybeBaseUrl = kj::mv(url);
2116    } else {
2117      return kj::str("Invalid base URL.");
2118    }
2119  }
2120 
2121  if (options.mode == ProcessInitOptions::Mode::PATTERN) {
2122    KJ_IF_SOME(protocol,
2123        chooseStr(kj::mv(init.protocol), options.protocol).map([](kj::String&& str) mutable {
2124      // It's silly but the URL spec always includes the : suffix in the value,
2125      // while the URLPattern spec always omits it. Silly specs.
2126      if (!str.size()) {
2127        return kj::mv(str);
2128      }
2129      return stripSuffixFromProtocol(str.asPtr());
2130    })) {
2131      result.protocol = kj::mv(protocol);
2132    }
2133    KJ_IF_SOME(username, chooseStr(kj::mv(init.username), options.username)) {
2134      result.username = kj::mv(username);
2135    }
2136    KJ_IF_SOME(password, chooseStr(kj::mv(init.password), options.password)) {
2137      result.password = kj::mv(password);
2138    }
2139    KJ_IF_SOME(hostname, chooseStr(kj::mv(init.hostname), options.hostname)) {
2140      result.hostname = kj::mv(hostname);
2141    }
2142    KJ_IF_SOME(port, chooseStr(kj::mv(init.port), options.port)) {
2143      result.port = kj::mv(port);
2144    }
2145    KJ_IF_SOME(pathname, chooseStr(kj::mv(init.pathname), options.pathname)) {
2146      if (!isAbsolutePathname(pathname)) {
2147        KJ_IF_SOME(url, maybeBaseUrl) {
2148          auto basePathname = url.getPathname();
2149          KJ_IF_SOME(index, basePathname.findLast('/')) {
2150            result.pathname = kj::str(basePathname.first(index + 1), pathname);
2151          } else {
2152            result.pathname = kj::str(basePathname);
2153          }
2154        } else {
2155          result.pathname = kj::mv(pathname);
2156        }
2157      } else {
2158        result.pathname = kj::mv(pathname);
2159      }
2160    }
2161    KJ_IF_SOME(search, chooseStr(kj::mv(init.search), options.search)) {
2162      if (search.size() > 0 && search[0] == '?') {
2163        result.search = kj::str(search.slice(1));
2164      } else {
2165        result.search = kj::mv(search);
2166      }
2167    }
2168    KJ_IF_SOME(hash, chooseStr(kj::mv(init.hash), options.hash)) {
2169      if (hash.size() > 0 && hash[0] == '#') {
2170        result.hash = kj::str(hash.slice(1));
2171      } else {
2172        result.hash = kj::mv(hash);
2173      }
2174    }
2175    return result;
2176  }
2177 
2178  KJ_DASSERT(options.mode == ProcessInitOptions::Mode::URL);
2179 
2180  // Things are a bit more complicated in this case. The individual components
2181  // of Init are interpreted as URL components. The processing here must convert
2182  // those into a canonical form. Unfortunately, however, it's not *quite* as
2183  // simple as constructing a URL string from the inputs, parsing it, and then
2184  // deconstructing the result. The validation rules per the URLPattern spec are
2185  // a bit different for some of the components than for the URL spec so we handle
2186  // each individually.
2187 
2188  bool isAbsolute = false;
2189  auto scratch = ([&]() -> kj::OneOf<Url, kj::String> {
2190    KJ_IF_SOME(protocol, chooseStr(kj::mv(init.protocol), options.protocol)) {
2191      // The protocol value we are given might not be valid. We'll check by
2192      // attempting to use it to parse a URL.
2193      bool emptyProtocol = protocol == "";
2194      auto str = kj::str((emptyProtocol ? "fake:"_kj : protocol.asPtr()),
2195          (emptyProtocol || protocol.asArray().back() == ':') ? "" : ":", "//a:b@fake-url");
2196      KJ_IF_SOME(parsed, Url::tryParse(str.asPtr())) {
2197        // Nice. We have a good protocol component. Let's set the normalized version
2198        // on the result and return the parsed URL to use as our temporary.
2199        if (!emptyProtocol) {
2200          result.protocol = stripSuffixFromProtocol(parsed.getProtocol());
2201        }
2202 
2203        // We set isAbsolute true here so that when we later want to normalize the
2204        // pathname, we know not to try to resolve the path relative to the base.
2205        isAbsolute = true;
2206        return kj::mv(parsed);
2207      } else {
2208        // Doh, parsing failed. The protocol component is invalid.
2209        return kj::str("Invalid URL protocol component");
2210      }
2211    } else {
2212      // There was not protocol component in the init or options. We still might
2213      // have a base URL protocol. If we do, we're going to use it to construct
2214      // our temporary URL we will use to canonicalize the rest. If we do not,
2215      // we'll use a fake URL scheme.
2216      KJ_IF_SOME(protocol, result.protocol) {
2217        // We only want to create the temporary URL here and return it.
2218        auto str = kj::str(protocol, "://fake-url");
2219        return KJ_ASSERT_NONNULL(Url::tryParse(str.asPtr()));
2220      } else {
2221        return KJ_ASSERT_NONNULL(Url::tryParse("fake://fake-url"_kj));
2222      }
2223    }
2224  })();
2225 
2226  KJ_SWITCH_ONEOF(scratch) {
2227    KJ_CASE_ONEOF(err, kj::String) {
2228      // Invalid URL protocol component.
2229      return kj::mv(err);
2230    }
2231    KJ_CASE_ONEOF(url, Url) {
2232      KJ_IF_SOME(username, chooseStr(kj::mv(init.username), options.username)) {
2233        if (!url.setUsername(username.asPtr())) {
2234          return kj::str("Invalid URL username component");
2235        }
2236        result.username = kj::str(url.getUsername());
2237      }
2238      KJ_IF_SOME(password, chooseStr(kj::mv(init.password), options.password)) {
2239        if (!url.setPassword(password.asPtr())) {
2240          return kj::str("Invalid URL password component");
2241        }
2242        result.password = kj::str(url.getPassword());
2243      }
2244      KJ_IF_SOME(hostname, chooseStr(kj::mv(init.hostname), options.hostname)) {
2245        if (!isValidHostnameInput(hostname) || !url.setHostname(hostname.asPtr())) {
2246          return kj::str("Invalid URL hostname component");
2247        }
2248        result.hostname = kj::str(url.getHostname());
2249      }
2250      KJ_IF_SOME(port, chooseStr(kj::mv(init.port), options.port)) {
2251        if (port.size() > 5 || !std::all_of(port.begin(), port.end(), isAsciiDigit)) {
2252          return kj::str("Invalid URL port component");
2253        }
2254        if (port.size() == 0) {
2255          url.setPort(kj::none);
2256        } else if (!url.setPort(kj::Maybe(port.asPtr()))) {
2257          return kj::str("Invalid URL port component");
2258        }
2259        result.port = kj::str(url.getPort());
2260      }
2261      KJ_IF_SOME(pathname, chooseStr(kj::mv(init.pathname), options.pathname)) {
2262        if (isAbsolute) {
2263          // isAbsolute is set only if we have an explicit protocol set for in init
2264          // or options. This tells us that we are not going to resolve the path
2265          // relative to the base URL at all.
2266          if (!url.setPathname(pathname.asPtr())) {
2267            return kj::str("Invalid URL pathname component");
2268          }
2269          result.pathname = kj::str(url.getPathname());
2270        } else {
2271          // Here, our init/options did not specify a protocol, so we're either relying
2272          // on the base URL or the fake. If we have a base URL, then, we want to resolve
2273          // the path relative to the base URL path.
2274          KJ_IF_SOME(base, maybeBaseUrl) {
2275            // If there is a base URL, then we'll normalize the path by attempting to
2276            // resolve against the base.
2277            KJ_IF_SOME(resolved, base.resolve(pathname.asPtr())) {
2278              result.pathname = kj::str(resolved.getPathname());
2279            } else {
2280              return kj::str("Invalid URL pathname component");
2281            }
2282          } else {
2283            if (!url.setPathname(pathname.asPtr())) {
2284              return kj::str("Invalid URL pathname component");
2285            }
2286            result.pathname = kj::str(url.getPathname());
2287          }
2288        }
2289      }
2290      KJ_IF_SOME(search, chooseStr(kj::mv(init.search), options.search)) {
2291        url.setSearch(kj::Maybe(search.asPtr()));
2292        // We slice here because the URL getter will always include the ? prefix
2293        // but the URLPattern spec does not want it.
2294        if (url.getSearch().size() > 0) {
2295          result.search = kj::str(url.getSearch().slice(1));
2296        } else {
2297          result.search = kj::String();
2298        }
2299      }
2300      KJ_IF_SOME(hash, chooseStr(kj::mv(init.hash), options.hash)) {
2301        url.setHash(kj::Maybe(hash.asPtr()));
2302        // We slice here because the URL getter will always include the # prefix
2303        // but the URLPattern spec does not want it.
2304        if (url.getHash().size() > 0) {
2305          result.hash = kj::str(url.getHash().slice(1));
2306        } else {
2307          result.hash = kj::String();
2308        }
2309      }
2310      return result;
2311    }
2312  }
2313  KJ_UNREACHABLE;
2314}
2315 
2316UrlPattern::Result<UrlPattern> UrlPattern::tryCompile(
2317    Init init, kj::Maybe<CompileOptions> maybeOptions) {
2318  auto options = maybeOptions.orDefault({});
2319  KJ_SWITCH_ONEOF(processInit(kj::mv(init))) {
2320    KJ_CASE_ONEOF(err, kj::String) {
2321      return kj::mv(err);
2322    }
2323    KJ_CASE_ONEOF(init, UrlPattern::Init) {
2324      return tryCompileInit(kj::mv(init), options);
2325    }
2326  }
2327  KJ_UNREACHABLE;
2328}
2329 
2330UrlPattern::Result<UrlPattern> UrlPattern::tryCompile(
2331    kj::StringPtr input, kj::Maybe<CompileOptions> maybeOptions) {
2332  auto options = maybeOptions.orDefault({});
2333  KJ_SWITCH_ONEOF(tryParseConstructorString(input, options)) {
2334    KJ_CASE_ONEOF(err, kj::String) {
2335      return kj::mv(err);
2336    }
2337    KJ_CASE_ONEOF(init, UrlPattern::Init) {
2338      KJ_SWITCH_ONEOF(processInit(kj::mv(init))) {
2339        KJ_CASE_ONEOF(err, kj::String) {
2340          return kj::mv(err);
2341        }
2342        KJ_CASE_ONEOF(init, UrlPattern::Init) {
2343          return tryCompileInit(kj::mv(init), options);
2344        }
2345      }
2346    }
2347  }
2348  KJ_UNREACHABLE;
2349}
2350 
2351UrlPattern::UrlPattern(kj::Array<Component> components, bool ignoreCase)
2352    : protocol(kj::mv(components[0])),
2353      username(kj::mv(components[1])),
2354      password(kj::mv(components[2])),
2355      hostname(kj::mv(components[3])),
2356      port(kj::mv(components[4])),
2357      pathname(kj::mv(components[5])),
2358      search(kj::mv(components[6])),
2359      hash(kj::mv(components[7])),
2360      ignoreCase(ignoreCase) {}
2361 
2362}  // namespace workerd::jsg
2363 
2364const workerd::jsg::Url operator""_url(const char* str, size_t size) {
2365  return KJ_ASSERT_NONNULL(workerd::jsg::Url::tryParse(kj::ArrayPtr<const char>(str, size)));
2366}