src/workerd/api/headers.c++

File
Blob: src/workerd/api/headers.c++

34.8 KB
1 #include "headers.h"
2  
3 #include "simdutf.h"
4  
5 #include <workerd/io/features.h>
6 #include <workerd/io/io-context.h>
7 #include <workerd/util/header-validation.h>
8 #include <workerd/util/strings.h>
9  
10 namespace workerd::api {
11  
12 namespace {
13  
14 #define COMMON_HEADERS(V)                                                                          \
15   V(ACCEPT_CHARSET, "accept-charset")                                                              \
16   V(ACCEPT_ENCODING, "accept-encoding")                                                            \
17   V(ACCEPT_LANGUAGE, "accept-language")                                                            \
18   V(ACCEPT_RANGES, "accept-ranges")                                                                \
19   V(ACCEPT, "accept")                                                                              \
20   V(ACCESS_CONTROL_ALLOW_ORIGIN, "access-control-allow-origin")                                    \
21   V(AGE, "age")                                                                                    \
22   V(ALLOW, "allow")                                                                                \
23   V(AUTHORIZATION, "authorization")                                                                \
24   V(CACHE_CONTROL, "cache-control")                                                                \
25   V(CONTENT_DISPOSITION, "content-disposition")                                                    \
26   V(CONTENT_ENCODING, "content-encoding")                                                          \
27   V(CONTENT_LANGUAGE, "content-language")                                                          \
28   V(CONTENT_LENGTH, "content-length")                                                              \
29   V(CONTENT_LOCATION, "content-location")                                                          \
30   V(CONTENT_RANGE, "content-range")                                                                \
31   V(CONTENT_TYPE, "content-type")                                                                  \
32   V(COOKIE, "cookie")                                                                              \
33   V(DATE, "date")                                                                                  \
34   V(ETAG, "etag")                                                                                  \
35   V(EXPECT, "expect")                                                                              \
36   V(EXPIRES, "expires")                                                                            \
37   V(FROM, "from")                                                                                  \
38   V(HOST, "host")                                                                                  \
39   V(IF_MATCH, "if-match")                                                                          \
40   V(IF_MODIFIED_SINCE, "if-modified-since")                                                        \
41   V(IF_NONE_MATCH, "if-none-match")                                                                \
42   V(IF_RANGE, "if-range")                                                                          \
43   V(IF_UNMODIFIED_SINCE, "if-unmodified-since")                                                    \
44   V(LAST_MODIFIED, "last-modified")                                                                \
45   V(LINK, "link")                                                                                  \
46   V(LOCATION, "location")                                                                          \
47   V(MAX_FORWARDS, "max-forwards")                                                                  \
48   V(PROXY_AUTHENTICATE, "proxy-authenticate")                                                      \
49   V(PROXY_AUTHORIZATION, "proxy-authorization")                                                    \
50   V(RANGE, "range")                                                                                \
51   V(REFERER, "referer")                                                                            \
52   V(REFRESH, "refresh")                                                                            \
53   V(RETRY_AFTER, "retry-after")                                                                    \
54   V(SERVER, "server")                                                                              \
55   V(SET_COOKIE, "set-cookie")                                                                      \
56   V(STRICT_TRANSPORT_SECURITY, "strict-transport-security")                                        \
57   V(TRANSFER_ENCODING, "transfer-encoding")                                                        \
58   V(USER_AGENT, "user-agent")                                                                      \
59   V(VARY, "vary")                                                                                  \
60   V(VIA, "via")                                                                                    \
61   V(WWW_AUTHENTICATE, "www-authenticate")
62  
63 // Constexpr array of lowercase common header names (must match CommonHeaderName enum order
64 // and must be kept in sync with the ordinal values defined in http-over-capnp.capnp). Since
65 // it is extremely unlikely that those will change often, we hardcode them here for runtime
66 // efficiency.
67 constexpr kj::StringPtr COMMON_HEADER_NAMES[] = {nullptr,  // 0: invalid
68 #define V(_, str) str##_kj,
69   COMMON_HEADERS(V)
70 #undef V
71 };
72  
73 // Static asserts for all of the common header names to ensure they are correct and in sync
74 // with the enum values.
75 static_assert(std::size(COMMON_HEADER_NAMES) == (Headers::MAX_COMMON_HEADER_ID + 1),
76     "COMMON_HEADER_NAMES must have an entry for each CommonHeaderName enum value");
77 #define V(id, str)                                                                                 \
78   static_assert(COMMON_HEADER_NAMES[static_cast<uint>(capnp::CommonHeaderName::id)] == str##_kj);
79 COMMON_HEADERS(V)
80 #undef V
81  
82 inline constexpr kj::StringPtr getCommonHeaderName(uint id) {
83   KJ_ASSERT(id > 0 && id <= Headers::MAX_COMMON_HEADER_ID, "Invalid common header ID");
84   return COMMON_HEADER_NAMES[id];
85 }
86  
87 // The CASE_CONVERSION_TABLE maps ASCII characters to their case conversion offset. For example,
88 // 'A' (0x41) maps to 32, which is the offset to convert it to 'a' (0x61). This allows us to perform
89 // branch-free case-insensitive comparisons and hashing by adding the offset to each character.
90 // For non-ASCII characters, the offset is 0, which means they are not modified. This table is
91 // used in the strcaseeq and caseInsensitiveHash functions below.
92 // clang-format off
93 constexpr kj::byte CASE_CONVERSION_TABLE[] = {
94    0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
95    0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
96    0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
97    0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
98    0, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
99   32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,  0,  0,  0,  0,  0,
100    0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
101    0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
102    0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
103    0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
104    0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
105    0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
106    0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
107    0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
108    0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
109    0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
110 };
111 // clang-format on
112  
113 // Bit paranoid but just to be safe...
114 static_assert(std::numeric_limits<kj::byte>::max() < kj::size(CASE_CONVERSION_TABLE));
115  
116 constexpr bool strcaseeq(kj::StringPtr a, kj::StringPtr b) {
117   if (a.size() != b.size()) return false;
118  
119   size_t i = 0;
120   while (i + sizeof(uint64_t) <= a.size()) {
121     // We assume that a is always lower-case to start.
122     uint64_t wa = (static_cast<uint64_t>(static_cast<uint8_t>(a[i + 0])) << 0) |
123         (static_cast<uint64_t>(static_cast<uint8_t>(a[i + 1])) << 8) |
124         (static_cast<uint64_t>(static_cast<uint8_t>(a[i + 2])) << 16) |
125         (static_cast<uint64_t>(static_cast<uint8_t>(a[i + 3])) << 24) |
126         (static_cast<uint64_t>(static_cast<uint8_t>(a[i + 4])) << 32) |
127         (static_cast<uint64_t>(static_cast<uint8_t>(a[i + 5])) << 40) |
128         (static_cast<uint64_t>(static_cast<uint8_t>(a[i + 6])) << 48) |
129         (static_cast<uint64_t>(static_cast<uint8_t>(a[i + 7])) << 56);
130  
131     uint8_t b0 = b[i + 0];
132     uint8_t b1 = b[i + 1];
133     uint8_t b2 = b[i + 2];
134     uint8_t b3 = b[i + 3];
135     uint8_t b4 = b[i + 4];
136     uint8_t b5 = b[i + 5];
137     uint8_t b6 = b[i + 6];
138     uint8_t b7 = b[i + 7];
139  
140     uint64_t normalized_b = (static_cast<uint64_t>(b0 + CASE_CONVERSION_TABLE[b0]) << 0) |
141         (static_cast<uint64_t>(b1 + CASE_CONVERSION_TABLE[b1]) << 8) |
142         (static_cast<uint64_t>(b2 + CASE_CONVERSION_TABLE[b2]) << 16) |
143         (static_cast<uint64_t>(b3 + CASE_CONVERSION_TABLE[b3]) << 24) |
144         (static_cast<uint64_t>(b4 + CASE_CONVERSION_TABLE[b4]) << 32) |
145         (static_cast<uint64_t>(b5 + CASE_CONVERSION_TABLE[b5]) << 40) |
146         (static_cast<uint64_t>(b6 + CASE_CONVERSION_TABLE[b6]) << 48) |
147         (static_cast<uint64_t>(b7 + CASE_CONVERSION_TABLE[b7]) << 56);
148  
149     if (wa != normalized_b) return false;
150     i += sizeof(uint64_t);
151   }
152  
153   for (; i < a.size(); ++i) {
154     char cb = b[i] + CASE_CONVERSION_TABLE[static_cast<kj::byte>(b[i])];
155     if (a[i] != cb) return false;
156   }
157   return true;
158 }
159  
160 // A FNV hash function that is case-insensitive.
161 // See: https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
162 constexpr uint caseInsensitiveHash(kj::StringPtr name) {
163   static constexpr uint32_t MULTIPLIER = 16777619u;
164   uint hash = 2166136261u;
165   size_t i = 0;
166  
167   while (i + sizeof(uint64_t) <= name.size()) {
168     uint8_t b0 = name[i + 0];
169     uint8_t b1 = name[i + 1];
170     uint8_t b2 = name[i + 2];
171     uint8_t b3 = name[i + 3];
172     uint8_t b4 = name[i + 4];
173     uint8_t b5 = name[i + 5];
174     uint8_t b6 = name[i + 6];
175     uint8_t b7 = name[i + 7];
176  
177     hash ^= b0 + CASE_CONVERSION_TABLE[b0];
178     hash *= MULTIPLIER;
179     hash ^= b1 + CASE_CONVERSION_TABLE[b1];
180     hash *= MULTIPLIER;
181     hash ^= b2 + CASE_CONVERSION_TABLE[b2];
182     hash *= MULTIPLIER;
183     hash ^= b3 + CASE_CONVERSION_TABLE[b3];
184     hash *= MULTIPLIER;
185     hash ^= b4 + CASE_CONVERSION_TABLE[b4];
186     hash *= MULTIPLIER;
187     hash ^= b5 + CASE_CONVERSION_TABLE[b5];
188     hash *= MULTIPLIER;
189     hash ^= b6 + CASE_CONVERSION_TABLE[b6];
190     hash *= MULTIPLIER;
191     hash ^= b7 + CASE_CONVERSION_TABLE[b7];
192     hash *= MULTIPLIER;
193  
194     i += sizeof(uint64_t);
195   }
196  
197   // Handle remaining bytes
198   for (; i < name.size(); ++i) {
199     uint8_t b = name[i];
200     hash ^= b + CASE_CONVERSION_TABLE[b];
201     hash *= MULTIPLIER;
202   }
203  
204   hash = (hash >> 16) ^ hash;
205   return hash;
206 }
207  
208 constexpr size_t HEADER_MAP_SIZE = 512;
209  
210 struct HeaderHashTable final {
211   struct Entry {
212     kj::StringPtr name;
213     uint id = 0;
214   };
215  
216   Entry entries[HEADER_MAP_SIZE] = {};
217  
218   // These are both calculated at compile time by the constexpr constructor.
219   size_t kMaxEntrySize = 0;
220   size_t kMinEntrySize = kj::maxValue;
221  
222   constexpr HeaderHashTable() {
223     for (uint i = 1; i <= Headers::MAX_COMMON_HEADER_ID; ++i) {
224       auto name = COMMON_HEADER_NAMES[i];
225       size_t slot = caseInsensitiveHash(name) % HEADER_MAP_SIZE;
226       entries[slot] = {name, i};
227       kMaxEntrySize = std::max(kMaxEntrySize, name.size());
228       kMinEntrySize = std::min(kMinEntrySize, name.size());
229     }
230   }
231  
232   constexpr uint find(kj::StringPtr name) const {
233     if (name.size() < kMinEntrySize || name.size() > kMaxEntrySize) {
234       return 0;
235     }
236     size_t slot = caseInsensitiveHash(name) % HEADER_MAP_SIZE;
237     const auto& entry = entries[slot];
238     if (entry.id != 0 && strcaseeq(entry.name, name)) {
239       return entry.id;
240     }
241     return 0;  // Not found
242   }
243  
244   // The isPerfectTest and isLowerTest are constexpr static assertions used
245   // only the verify correctness of the hash table at compile time.
246   constexpr bool isPerfectTest() const {
247     for (uint i = 1; i <= Headers::MAX_COMMON_HEADER_ID; ++i) {
248       auto name = COMMON_HEADER_NAMES[i];
249       size_t slot = caseInsensitiveHash(name) % HEADER_MAP_SIZE;
250       if (entries[slot].id != i) return false;
251       if (!strcaseeq(entries[slot].name, name)) return false;
252     }
253     return true;
254   }
255  
256   constexpr bool isLowerTest() const {
257     for (uint i = 1; i <= Headers::MAX_COMMON_HEADER_ID; ++i) {
258       auto name = COMMON_HEADER_NAMES[i];
259       for (char c: name) {
260         if ('A' <= c && c <= 'Z') return false;
261       }
262     }
263     return true;
264   }
265 };
266  
267 constexpr HeaderHashTable HEADER_HASH_TABLE;
268 static_assert(HEADER_HASH_TABLE.kMaxEntrySize == 27);
269 static_assert(HEADER_HASH_TABLE.kMinEntrySize == 3);
270 static_assert(HEADER_HASH_TABLE.isPerfectTest());
271 static_assert(HEADER_HASH_TABLE.isLowerTest());
272 static_assert(HEADER_HASH_TABLE.find("accept-charset"_kj) == 1);
273 static_assert(HEADER_HASH_TABLE.find("AcCePt-ChArSeT"_kj) == 1);
274 static_assert(std::size(COMMON_HEADER_NAMES) == (Headers::MAX_COMMON_HEADER_ID + 1));
275  
276 void maybeWarnIfBadHeaderString(kj::StringPtr name, kj::StringPtr str) {
277   KJ_IF_SOME(context, IoContext::tryCurrent()) {
278     if (context.hasWarningHandler()) {
279       if (!simdutf::validate_ascii(str.begin(), str.size())) {
280         // The string contains non-ASCII characters. While any 8-bit value is technically valid
281         // in HTTP headers, we encode header strings as UTF-8, so we want to warn the user that
282         // their header name/value may not be what they may expect based on what browsers do.
283         auto utf8Hex = kj::strArray(
284             KJ_MAP(b, str) { return kj::str("\\x", kj::hex(static_cast<kj::byte>(b))); }, "");
285         context.logWarning(kj::str("A header value for \"", name,
286             "\" contains non-ASCII "
287             "characters: \"",
288             str, "\" (raw bytes: \"", utf8Hex,
289             "\"). As a quirk to support Unicode, we are encoding "
290             "values as UTF-8 in the header, but in a browser this would likely result in a "
291             "TypeError exception. Consider encoding this string in ASCII for compatibility with "
292             "browser implementations of the Fetch specification."));
293       }
294     }
295   }
296 }
297  
298 // Left- and right-trim HTTP whitespace from `value`.
299 kj::String normalizeHeaderValue(kj::StringPtr name, kj::String value) {
300   // Fast path: if empty, return as-is
301   if (value.size() == 0) {
302     return kj::mv(value);
303   }
304  
305   char* begin = value.begin();
306   char* end = value.end();
307  
308   while (begin < end && util::isHttpWhitespace(*begin)) {
309     ++begin;
310   }
311   while (begin < end && util::isHttpWhitespace(*(end - 1))) {
312     --end;
313   }
314  
315   size_t newSize = end - begin;
316   if (newSize == value.size()) {
317     JSG_REQUIRE(workerd::util::isValidHeaderValue(value), TypeError, "Invalid header value.");
318     maybeWarnIfBadHeaderString(name, value);
319     return kj::mv(value);
320   }
321  
322   auto trimmed = kj::ArrayPtr(begin, newSize);
323   JSG_REQUIRE(workerd::util::isValidHeaderValue(trimmed), TypeError, "Invalid header value.");
324   maybeWarnIfBadHeaderString(name, value);
325   // By attaching the original array to the trimmed view, we keep the original allocation alive
326   // and prevent an unnecessary copy.
327   return kj::str(trimmed.attach(value.releaseArray()));
328 }
329  
330 Headers::HeaderKey getHeaderKeyFor(kj::StringPtr name) {
331   if (uint commonId = HEADER_HASH_TABLE.find(name)) {
332     KJ_DASSERT(commonId > 0 && commonId <= Headers::MAX_COMMON_HEADER_ID);
333     return commonId;
334   }
335  
336   for (char c: name) {
337     JSG_REQUIRE(util::isHttpTokenChar(c), TypeError, "Invalid header name.");
338   }
339  
340   // Not a common header, so allocate lowercase copy for uncommon header
341   return toLower(name);
342 }
343 }  // namespace
344  
345 Headers::Headers(jsg::Lock& js, jsg::Dict<kj::String, kj::String> dict): guard(Guard::NONE) {
346   // Because the headers might end up in either of our two tables,
347   // we can't really reserve space for them up front.
348   for (auto& field: dict.fields) {
349     append(js, kj::mv(field.name), kj::mv(field.value));
350   }
351 }
352  
353 Headers::Headers(jsg::Lock& js, const Headers& other): guard(Guard::NONE) {
354   for (kj::uint i = 1; i < other.commonHeaders.size(); i++) {
355     commonHeaders[i] =
356         other.commonHeaders[i].map([](const kj::Own<Header>& h) { return h->clone(); });
357   }
358   uncommonHeaders.reserve(other.uncommonHeaders.size());
359   for (auto& [key, header]: other.uncommonHeaders) {
360     // It should not be possible to have duplicate keys here.
361     uncommonHeaders.insert(kj::str(key), header->clone());
362   }
363 }
364  
365 Headers::Headers(jsg::Lock& js, const kj::HttpHeaders& other, Guard guard): guard(guard) {
366   // TODO(perf): Once kj::HttpHeaders supports an API for getting the CommonHeaderName directly
367   // from the headers, we can optimize this to avoid looking up the common header IDs again,
368   // making this constructor more efficient when copying common headers from kj::HttpHeaders.
369   other.forEach([this, &js](auto name, auto value) {
370     // We have to copy the strings here but we can avoid normalizing and validating since
371     // they presumably already went through that process when they were added to the
372     // kj::HttpHeader instance.
373     appendUnguarded(js, kj::str(name), kj::str(value));
374   });
375 }
376  
377 kj::Maybe<Headers::Header&> Headers::tryGetHeader(const HeaderKey& key) {
378   KJ_SWITCH_ONEOF(key) {
379     KJ_CASE_ONEOF(idx, kj::uint) {
380       return commonHeaders[idx].map([](kj::Own<Header>& header) -> Header& { return *header; });
381     }
382     KJ_CASE_ONEOF(name, kj::String) {
383       return uncommonHeaders.find(name).map(
384           [](kj::Own<Header>& header) -> Header& { return *header; });
385     }
386   }
387   KJ_UNREACHABLE;
388 }
389  
390 jsg::Ref<Headers> Headers::clone(jsg::Lock& js) const {
391   auto result = js.alloc<Headers>(js, *this);
392   result->guard = guard;
393   return kj::mv(result);
394 }
395  
396 // Fill in the given HttpHeaders with these headers. Note that strings are inserted by
397 // reference, so the output must be consumed immediately.
398 void Headers::shallowCopyTo(kj::HttpHeaders& out) {
399   for (kj::uint i = 1; i < commonHeaders.size(); i++) {
400     KJ_IF_SOME(header, commonHeaders[i]) {
401       KJ_IF_SOME(name, header->name) {
402         for (auto& value: header->values) {
403           out.addPtrPtr(name, value);
404         }
405       } else {
406         auto name = getCommonHeaderName(i);
407         for (auto& value: header->values) {
408           out.addPtrPtr(name, value);
409         }
410       }
411     }
412   }
413  
414   // This is unfortunate... but we have to sort the uncommon headers by name
415   // before passing them off to kj::HttpHeaders...While the actual header order
416   // (for different header names) is not meaningful in HTTP, we have tests that
417   // expect a certain order for reproducibility.
418   struct Entry {
419     kj::StringPtr name;
420     kj::StringPtr value;
421   };
422   kj::Vector<Entry> entries(uncommonHeaders.size());
423   for (auto& header: uncommonHeaders) {
424     KJ_IF_SOME(name, header.value->name) {
425       for (auto& value: header.value->values) {
426         entries.add(Entry{.name = name, .value = value});
427       }
428     } else {
429       for (auto& value: header.value->values) {
430         entries.add(Entry{.name = header.key, .value = value});
431       }
432     }
433   }
434   std::stable_sort(entries.begin(), entries.end(),
435       [](const Entry& a, const Entry& b) { return a.name < b.name; });
436  
437   for (const auto& entry: entries) {
438     out.addPtrPtr(entry.name, entry.value);
439   }
440 }
441  
442 kj::Array<Headers::DisplayedHeader> Headers::getDisplayedHeaders(jsg::Lock& js) {
443   auto getSetCookie = FeatureFlags::get(js).getHttpHeadersGetSetCookie();
444  
445   size_t reserved = 0;
446  
447   for (kj::uint i = 1; i < commonHeaders.size(); i++) {
448     KJ_IF_SOME(header, commonHeaders[i]) {
449       if (getSetCookie && i == static_cast<uint>(capnp::CommonHeaderName::SET_COOKIE)) {
450         reserved += header->values.size();
451       } else {
452         reserved += 1;
453       }
454     }
455   }
456   for (auto& header: uncommonHeaders) {
457     reserved += header.value->values.size();
458   }
459   kj::Vector<Headers::DisplayedHeader> vec(reserved);
460  
461   for (kj::uint i = 1; i < commonHeaders.size(); i++) {
462     auto name = getCommonHeaderName(i);
463     KJ_IF_SOME(header, commonHeaders[i]) {
464       if (getSetCookie && i == static_cast<uint>(capnp::CommonHeaderName::SET_COOKIE)) {
465         for (auto& value: header->values) {
466           vec.add(Headers::DisplayedHeader{
467             .key = kj::str(name),
468             .value = kj::str(value),
469           });
470         }
471       } else {
472         vec.add(Headers::DisplayedHeader{
473           .key = kj::str(name),
474           .value = kj::strArray(header->values, ", "),
475         });
476       }
477     }
478   }
479  
480   for (auto& header: uncommonHeaders) {
481     vec.add(Headers::DisplayedHeader{
482       .key = kj::str(header.key),
483       .value = kj::strArray(header.value->values, ", "),
484     });
485   }
486  
487   auto ret = vec.releaseAsArray();
488   std::sort(ret.begin(), ret.end(), [](const auto& a, const auto& b) { return a.key < b.key; });
489   return kj::mv(ret);
490 }
491  
492 jsg::Ref<Headers> Headers::constructor(jsg::Lock& js, jsg::Optional<Initializer> init) {
493   using StringDict = jsg::Dict<kj::String, kj::String>;
494  
495   KJ_IF_SOME(i, init) {
496     KJ_SWITCH_ONEOF(kj::mv(i)) {
497       KJ_CASE_ONEOF(dict, StringDict) {
498         return js.alloc<Headers>(js, kj::mv(dict));
499       }
500       KJ_CASE_ONEOF(headers, jsg::Ref<Headers>) {
501         return js.alloc<Headers>(js, *headers);
502         // It's important to note here that we are treating the Headers object
503         // as a special case here. Per the fetch spec, we *should* be grabbing
504         // the Symbol.iterator off the Headers object and interpreting it as
505         // a Sequence<Sequence<kj::String>> (as in the StringPairs case
506         // below). However, special casing Headers like we do here is more
507         // performant and has other side effects such as preserving the casing
508         // of header names that have been received.
509         //
510         // This does mean that we fail one of the more pathological (and kind
511         // of weird) Web Platform Tests for this API:
512         //
513         //   const h = new Headers();
514         //   h[Symbol.iterator] = function * () { yield ["test", "test"]; };
515         //   const headers = new Headers(h);
516         //   console.log(headers.has("test"));
517         //
518         // The spec would say headers.has("test") here should be true. With our
519         // implementation here, however, we are ignoring the Symbol.iterator so
520         // the test fails.
521       }
522       KJ_CASE_ONEOF(pairs, StringPairs) {
523         auto dict = KJ_MAP(entry, pairs) {
524           JSG_REQUIRE(entry.size() == 2, TypeError,
525               "To initialize a Headers object from a sequence, each inner sequence "
526               "must have exactly two elements.");
527           return StringDict::Field{kj::mv(entry[0]), kj::mv(entry[1])};
528         };
529         return js.alloc<Headers>(js, StringDict{kj::mv(dict)});
530       }
531     }
532   }
533  
534   return js.alloc<Headers>();
535 }
536  
537 kj::Maybe<kj::String> Headers::get(jsg::Lock& js, kj::String name) {
538   return getPtr(js, name);
539 }
540  
541 kj::Maybe<kj::String> Headers::getPtr(jsg::Lock& js, kj::StringPtr name) {
542   return tryGetHeader(getHeaderKeyFor(name)).map([](Header& header) {
543     return kj::strArray(header.values, ", ");
544   });
545 }
546  
547 kj::Maybe<kj::String> Headers::getCommon(jsg::Lock& js, capnp::CommonHeaderName idx) {
548   kj::uint index = static_cast<kj::uint>(idx);
549   KJ_DASSERT(index <= Headers::MAX_COMMON_HEADER_ID);
550   return commonHeaders[index].map([](auto& header) { return kj::strArray(header->values, ", "); });
551 }
552  
553 kj::Array<kj::StringPtr> Headers::getSetCookie() {
554   auto& header = commonHeaders[static_cast<kj::uint>(capnp::CommonHeaderName::SET_COOKIE)];
555   KJ_IF_SOME(h, header) {
556     return KJ_MAP(value, h->values) { return value.asPtr(); };
557   }
558   return nullptr;
559 }
560  
561 kj::Array<kj::StringPtr> Headers::getAll(kj::String name) {
562   if (!strcaseeq("set-cookie"_kj, name)) {
563     JSG_FAIL_REQUIRE(TypeError, "getAll() can only be used with the header name \"Set-Cookie\".");
564   }
565  
566   // getSetCookie() is the standard API here. getAll(...) is our legacy non-standard extension
567   // for the same use case. We continue to support getAll for backwards compatibility but moving
568   // forward users really should be using getSetCookie.
569   return getSetCookie();
570 }
571  
572 bool Headers::has(kj::String name) {
573   return tryGetHeader(getHeaderKeyFor(name)) != kj::none;
574 }
575  
576 bool Headers::hasCommon(capnp::CommonHeaderName idx) {
577   kj::uint index = static_cast<kj::uint>(idx);
578   KJ_DASSERT(index <= Headers::MAX_COMMON_HEADER_ID);
579   return commonHeaders[index] != kj::none;
580 }
581  
582 void Headers::set(jsg::Lock& js, kj::String name, kj::String value) {
583   checkGuard();
584   value = normalizeHeaderValue(name, kj::mv(value));
585   setUnguarded(js, kj::mv(name), kj::mv(value));
586 }
587  
588 void Headers::setUnguarded(jsg::Lock& js, kj::String name, kj::String value) {
589   KJ_SWITCH_ONEOF(getHeaderKeyFor(name)) {
590     KJ_CASE_ONEOF(id, kj::uint) {
591       KJ_IF_SOME(existing, commonHeaders[id]) {
592         existing->values.resize(1);
593         existing->values[0] = kj::mv(value);
594       } else {
595         auto& created = commonHeaders[id].emplace(kj::heap(Header()));
596         if (name != getCommonHeaderName(id)) {
597           created->name = kj::mv(name);
598         }
599         created->values.resize(1);
600         created->values[0] = kj::mv(value);
601       }
602       return;
603     }
604     KJ_CASE_ONEOF(n, kj::String) {
605       using Ret = decltype(uncommonHeaders)::Entry;
606       auto& header = uncommonHeaders.findOrCreate(n, [&] -> Ret {
607         kj::Maybe<kj::String> maybeName;
608         if (name != n) {
609           maybeName = kj::mv(name);
610         }
611         return Ret{
612           .key = kj::mv(n),
613           .value = kj::heap(Header(kj::mv(maybeName))),
614         };
615       });
616       header->values.resize(1);
617       header->values[0] = kj::mv(value);
618       return;
619     }
620   }
621   KJ_UNREACHABLE;
622 }
623  
624 void Headers::setCommon(capnp::CommonHeaderName idx, kj::String value) {
625   kj::uint index = static_cast<kj::uint>(idx);
626   KJ_DASSERT(index <= Headers::MAX_COMMON_HEADER_ID);
627   KJ_IF_SOME(existing, commonHeaders[index]) {
628     existing->values.resize(1);
629     existing->values[0] = kj::mv(value);
630   } else {
631     auto& created = commonHeaders[index].emplace(kj::heap(Header()));
632     created->values.resize(1);
633     created->values[0] = kj::mv(value);
634   }
635 }
636  
637 void Headers::append(jsg::Lock& js, kj::String name, kj::String value) {
638   checkGuard();
639   value = normalizeHeaderValue(name, kj::mv(value));
640   appendUnguarded(js, kj::mv(name), kj::mv(value));
641 }
642  
643 void Headers::appendUnguarded(jsg::Lock& js, kj::String name, kj::String value) {
644   KJ_SWITCH_ONEOF(getHeaderKeyFor(name)) {
645     KJ_CASE_ONEOF(id, kj::uint) {
646       KJ_IF_SOME(existing, commonHeaders[id]) {
647         existing->values.add(kj::mv(value));
648       } else {
649         auto& created = commonHeaders[id].emplace(kj::heap(Header()));
650         if (name != getCommonHeaderName(id)) {
651           created->name = kj::mv(name);
652         }
653         created->values.resize(1);
654         created->values[0] = kj::mv(value);
655       }
656       return;
657     }
658     KJ_CASE_ONEOF(n, kj::String) {
659       KJ_IF_SOME(existing, uncommonHeaders.find(n)) {
660         existing->values.add(kj::mv(value));
661       } else {
662         using Ret = decltype(uncommonHeaders)::Entry;
663         auto& header = uncommonHeaders.findOrCreate(n, [&] -> Ret {
664           kj::Maybe<kj::String> maybeName;
665           if (name != n) {
666             maybeName = kj::mv(name);
667           }
668           return Ret{
669             .key = kj::mv(n),
670             .value = kj::heap(Header(kj::mv(maybeName))),
671           };
672         });
673         header->values.add(kj::mv(value));
674       }
675       return;
676     }
677   }
678   KJ_UNREACHABLE;
679 }
680  
681 void Headers::delete_(kj::String name) {
682   checkGuard();
683   KJ_SWITCH_ONEOF(getHeaderKeyFor(name)) {
684     KJ_CASE_ONEOF(id, kj::uint) {
685       commonHeaders[id] = kj::none;
686       return;
687     }
688     KJ_CASE_ONEOF(n, kj::String) {
689       uncommonHeaders.erase(n);
690       return;
691     }
692   }
693   KJ_UNREACHABLE;
694 }
695  
696 void Headers::deleteCommon(capnp::CommonHeaderName idx) {
697   kj::uint index = static_cast<kj::uint>(idx);
698   KJ_DASSERT(index <= Headers::MAX_COMMON_HEADER_ID);
699   commonHeaders[index] = kj::none;
700 }
701  
702 // There are a couple implementation details of the Headers iterators worth calling out.
703 //
704 // 1. Each iterator gets its own copy of the keys and/or values of the headers. While nauseating
705 //    from a performance perspective, this solves both the iterator -> iterable lifetime dependence
706 //    and the iterator invalidation issue: i.e., it's impossible for a user to unsafely modify the
707 //    Headers data structure while iterating over it, because they are simply two separate data
708 //    structures. By empirical testing, this seems to be how Chrome implements Headers iteration.
709 //
710 //    Other alternatives bring their own pitfalls. We could store a Ref of the parent Headers
711 //    object, solving the lifetime issue. To solve the iterator invalidation issue, we could store a
712 //    copy of the currently-iterated-over key and use std::upper_bound() to find the next entry
713 //    every time we want to increment the iterator (making the increment operation O(lg n) rather
714 //    than O(1)); or we could make each Header entry in the map store a set of back-pointers to all
715 //    live iterators pointing to it, with delete_() incrementing all iterators in the set whenever
716 //    it deletes a header entry. Neither hack appealed to me.
717 //
718 // 2. Notice that the next() member function of the iterator classes moves the string(s) they
719 //    contain, rather than making a copy of them as in the FormData iterators. This is safe to do
720 //    because, unlike FormData, these iterators have their own copies of the strings, and since they
721 //    are forward-only iterators, we know we won't need the strings again.
722 //
723 // TODO(perf): On point 1, perhaps we could avoid most copies by using a copy-on-write strategy
724 //   applied to the header map elements? We'd still copy the whole data structure to avoid iterator
725 //   invalidation, but the elements would be cheaper to copy.
726  
727 jsg::Ref<Headers::EntryIterator> Headers::entries(jsg::Lock& js) {
728   return js.alloc<EntryIterator>(IteratorState<DisplayedHeader>{getDisplayedHeaders(js)});
729 }
730 jsg::Ref<Headers::KeyIterator> Headers::keys(jsg::Lock& js) {
731   auto headers = getDisplayedHeaders(js);
732   kj::Vector<kj::String> keys(headers.size());
733   for (auto& header: headers) {
734     keys.add(kj::mv(header.key));
735   };
736   return js.alloc<KeyIterator>(IteratorState<kj::String>(keys.releaseAsArray()));
737 }
738 jsg::Ref<Headers::ValueIterator> Headers::values(jsg::Lock& js) {
739   // Annoyingly, the spec requires that the values iterator still be sorted by key.
740   // To make this easiest, let's grab the displayed headers and then extract the values.
741   // the getDisplayedHeaders() function does the sorting for us at the cost of an extra
742   // copy of the names. Fortunately, enumerating by value is likely way less common than
743   // other forms of iteration so the cost should be acceptable.
744   auto headers = getDisplayedHeaders(js);
745   kj::Vector<kj::String> values(headers.size());
746   for (auto& header: headers) {
747     values.add(kj::mv(header.value));
748   };
749   return js.alloc<ValueIterator>(IteratorState<kj::String>(values.releaseAsArray()));
750 }
751  
752 void Headers::forEach(jsg::Lock& js,
753     jsg::Function<void(kj::StringPtr, kj::StringPtr, jsg::Ref<Headers>)> callback,
754     jsg::Optional<jsg::Value> thisArg) {
755   auto receiver = js.v8Undefined();
756   KJ_IF_SOME(arg, thisArg) {
757     auto handle = arg.getHandle(js);
758     if (!handle->IsNullOrUndefined()) {
759       receiver = handle;
760     }
761   }
762   callback.setReceiver(js.v8Ref(receiver));
763  
764   for (auto& entry: getDisplayedHeaders(js)) {
765     callback(js, entry.value, entry.key, JSG_THIS);
766   }
767 }
768  
769 bool Headers::inspectImmutable() {
770   return guard != Guard::NONE;
771 }
772  
773 void Headers::visitForMemoryInfo(jsg::MemoryTracker& tracker) const {
774   for (const auto& header: commonHeaders) {
775     tracker.trackField("header", header);
776   }
777   for (const auto& header: uncommonHeaders) {
778     tracker.trackField(nullptr, header.value);
779   }
780 }
781  
782 // -----------------------------------------------------------------------------
783 // serialization of headers
784 //
785 // http-over-capnp.capnp has a nice list of common header names, taken from the HTTP/2 standard.
786 // We'll use it as an optimization.
787 //
788 // Note that using numeric IDs for headers implies we lose the original capitalization. However,
789 // the JS Headers API doesn't actually give the application any way to observe the capitalization
790 // of header names -- it only becomes relevant when serializing over HTTP/1.1. And at that point,
791 // we are actually free to change the capitalization anyway, and we commonly do (KJ itself will
792 // normalize capitalization of all registered headers, and http-over-capnp also loses
793 // capitalization). So, it's certainly not worth it to try to keep the original capitalization
794 // across serialization.
795  
796 void Headers::serialize(jsg::Lock& js, jsg::Serializer& serializer) {
797   // We serialize as a series of key-value pairs. Each value is a length-delimited string. Each key
798   // is a common header ID, or the value zero to indicate an uncommon header, which is then
799   // followed by a length-delimited name.
800  
801   serializer.writeRawUint32(static_cast<uint>(guard));
802  
803   // Write the count of headers.
804   uint count = 0;
805   for (auto& header: commonHeaders) {
806     KJ_IF_SOME(h, header) {
807       count += h->values.size();
808     }
809   }
810   for (auto& header: uncommonHeaders) {
811     count += header.value->values.size();
812   }
813   serializer.writeRawUint32(count);
814  
815   // Now write key/values.
816   for (kj::uint i = 1; i < commonHeaders.size(); i++) {
817     KJ_IF_SOME(header, commonHeaders[i]) {
818       for (auto& value: header->values) {
819         serializer.writeRawUint32(i);
820         serializer.writeLengthDelimited(value);
821       }
822     }
823   }
824   for (auto& header: uncommonHeaders) {
825     auto name = ([&] -> kj::StringPtr {
826       KJ_IF_SOME(name, header.value->name) {
827         return name;
828       } else {
829         return header.key;
830       }
831     })();
832     for (auto& value: header.value->values) {
833       serializer.writeRawUint32(0);
834       serializer.writeLengthDelimited(name);
835       serializer.writeLengthDelimited(value);
836     }
837   }
838 }
839  
840 jsg::Ref<Headers> Headers::deserialize(
841     jsg::Lock& js, rpc::SerializationTag tag, jsg::Deserializer& deserializer) {
842   auto result = js.alloc<Headers>();
843   uint guard = deserializer.readRawUint32();
844   KJ_REQUIRE(guard <= static_cast<uint>(Guard::NONE), "unknown guard value");
845  
846   uint count = deserializer.readRawUint32();
847   JSG_REQUIRE(count <= 1024, DOMDataCloneError,
848       "Deserialization failed: header count exceeds maximum (", count, ")");
849  
850   for (auto i KJ_UNUSED: kj::zeroTo(count)) {
851     uint commonId = deserializer.readRawUint32();
852     kj::String name;
853     if (commonId == 0) {
854       name = deserializer.readLengthDelimitedString();
855     } else {
856       KJ_ASSERT(commonId <= Headers::MAX_COMMON_HEADER_ID);
857       name = kj::str(getCommonHeaderName(commonId));
858     }
859  
860     auto value = deserializer.readLengthDelimitedString();
861  
862     // TODO(performance): We can avoid some copies here by constructing the
863     // the Header entry directly using information from the deserializer
864     // directly without relying on append.
865     result->appendUnguarded(js, kj::mv(name), kj::mv(value));
866   }
867  
868   // Don't actually set the guard until here because it may block the ability to call `append()`.
869   result->guard = static_cast<Guard>(guard);
870  
871   return result;
872 }
873  
874 }  // namespace workerd::api