chore: align `Headers` to spec (#10199)

This commit aligns `Headers` to spec. It also removes the now unused
03_dom_iterable.js file. We now pass all relevant `Headers` WPT. We do
not implement any sort of header filtering, as we are a server side
runtime.

This is likely not the most efficient implementation of `Headers` yet.
It is however spec compliant. Once all the APIs in the `HTTP` hot loop
are correct we can start optimizing them. It is likely that this commit
reduces bench throughput temporarily.

1 files changed, 305 insertions, 197 deletions

diff --git a/op_crates/fetch/20_headers.js b/op_crates/fetch/20_headers.js
index df11d40b6..ce46e5dee 100644
--- a/op_crates/fetch/20_headers.js
+++ b/op_crates/fetch/20_headers.js
@@ -1,247 +1,327 @@
 // Copyright 2018-2021 the Deno authors. All rights reserved. MIT license.
+
+// @ts-check
+/// <reference path="../webidl/internal.d.ts" />
+/// <reference path="../web/internal.d.ts" />
+/// <reference path="../file/internal.d.ts" />
+/// <reference path="../file/lib.deno_file.d.ts" />
+/// <reference path="./internal.d.ts" />
+/// <reference path="./11_streams_types.d.ts" />
+/// <reference path="./lib.deno_fetch.d.ts" />
+/// <reference lib="esnext" />
 "use strict";
 
 ((window) => {
-  const { DomIterableMixin } = window.__bootstrap.domIterable;
-  const { requiredArguments } = window.__bootstrap.fetchUtil;
-
-  // From node-fetch
-  // Copyright (c) 2016 David Frank. MIT License.
-  const invalidTokenRegex = /[^\^_`a-zA-Z\-0-9!#$%&'*+.|~]/;
-  const invalidHeaderCharRegex = /[^\t\x20-\x7e\x80-\xff]/;
-
-  function isHeaders(value) {
-    // eslint-disable-next-line @typescript-eslint/no-use-before-define
-    return value instanceof Headers;
-  }
+  const webidl = window.__bootstrap.webidl;
+  const {
+    HTTP_WHITESPACE_PREFIX_RE,
+    HTTP_WHITESPACE_SUFFIX_RE,
+    HTTP_TOKEN_CODE_POINT_RE,
+    byteLowerCase,
+  } = window.__bootstrap.infra;
 
-  const headersData = Symbol("headers data");
+  const _headerList = Symbol("header list");
+  const _iterableHeaders = Symbol("iterable headers");
+  const _guard = Symbol("guard");
 
-  // TODO(bartlomieju): headerGuard? Investigate if it is needed
-  // node-fetch did not implement this but it is in the spec
-  function normalizeParams(name, value) {
-    name = String(name).toLowerCase();
-    value = String(value).trim();
-    return [name, value];
-  }
+  /**
+   * @typedef Header
+   * @type {[string, string]}
+   */
 
-  // The following name/value validations are copied from
-  // https://github.com/bitinn/node-fetch/blob/master/src/headers.js
-  // Copyright (c) 2016 David Frank. MIT License.
-  function validateName(name) {
-    if (invalidTokenRegex.test(name) || name === "") {
-      throw new TypeError(`${name} is not a legal HTTP header name`);
-    }
-  }
+  /**
+   * @typedef HeaderList
+   * @type {Header[]}
+   */
 
-  function validateValue(value) {
-    if (invalidHeaderCharRegex.test(value)) {
-      throw new TypeError(`${value} is not a legal HTTP header value`);
-    }
+  /**
+   * @typedef {string} potentialValue 
+   * @returns {string}
+   */
+  function normalizeHeaderValue(potentialValue) {
+    potentialValue = potentialValue.replaceAll(HTTP_WHITESPACE_PREFIX_RE, "");
+    potentialValue = potentialValue.replaceAll(HTTP_WHITESPACE_SUFFIX_RE, "");
+    return potentialValue;
   }
 
-  /** Appends a key and value to the header list.
- *
- * The spec indicates that when a key already exists, the append adds the new
- * value onto the end of the existing value.  The behaviour of this though
- * varies when the key is `set-cookie`.  In this case, if the key of the cookie
- * already exists, the value is replaced, but if the key of the cookie does not
- * exist, and additional `set-cookie` header is added.
- *
- * The browser specification of `Headers` is written for clients, and not
- * servers, and Deno is a server, meaning that it needs to follow the patterns
- * expected for servers, of which a `set-cookie` header is expected for each
- * unique cookie key, but duplicate cookie keys should not exist. */
-  function dataAppend(
-    data,
-    key,
-    value,
-  ) {
-    for (let i = 0; i < data.length; i++) {
-      const [dataKey] = data[i];
-      if (key === "set-cookie" && dataKey === "set-cookie") {
-        const [, dataValue] = data[i];
-        const [dataCookieKey] = dataValue.split("=");
-        const [cookieKey] = value.split("=");
-        if (dataCookieKey === cookieKey) {
-          data[i][1] = value;
-          return;
-        }
-      } else {
-        if (dataKey === key) {
-          data[i][1] += `, ${value}`;
-          return;
+  /**
+   * @param {Headers} headers
+   * @param {HeadersInit} object
+   */
+  function fillHeaders(headers, object) {
+    if (Array.isArray(object)) {
+      for (const header of object) {
+        if (header.length !== 2) {
+          throw new TypeError(
+            `Invalid header. Length must be 2, but is ${header.length}`,
+          );
         }
+        appendHeader(headers, header[0], header[1]);
+      }
+    } else {
+      for (const key of Object.keys(object)) {
+        appendHeader(headers, key, object[key]);
       }
     }
-    data.push([key, value]);
   }
 
-  /** Gets a value of a key in the headers list.
- *
- * This varies slightly from spec behaviour in that when the key is `set-cookie`
- * the value returned will look like a concatenated value, when in fact, if the
- * headers were iterated over, each individual `set-cookie` value is a unique
- * entry in the headers list. */
-  function dataGet(
-    data,
-    key,
-  ) {
-    const setCookieValues = [];
-    for (const [dataKey, value] of data) {
-      if (dataKey === key) {
-        if (key === "set-cookie") {
-          setCookieValues.push(value);
-        } else {
-          return value;
-        }
-      }
+  /**
+   * https://fetch.spec.whatwg.org/#concept-headers-append
+   * @param {Headers} headers
+   * @param {string} name 
+   * @param {string} value 
+   */
+  function appendHeader(headers, name, value) {
+    // 1.
+    value = normalizeHeaderValue(value);
+
+    // 2.
+    if (!HTTP_TOKEN_CODE_POINT_RE.test(name)) {
+      throw new TypeError("Header name is not valid.");
     }
-    if (setCookieValues.length) {
-      return setCookieValues.join(", ");
+    if (
+      value.includes("\x00") || value.includes("\x0A") || value.includes("\x0D")
+    ) {
+      throw new TypeError("Header value is not valid.");
     }
-    return undefined;
-  }
 
-  /** Sets a value of a key in the headers list.
- *
- * The spec indicates that the value should be replaced if the key already
- * exists.  The behaviour here varies, where if the key is `set-cookie` the key
- * of the cookie is inspected, and if the key of the cookie already exists,
- * then the value is replaced.  If the key of the cookie is not found, then
- * the value of the `set-cookie` is added to the list of headers.
- *
- * The browser specification of `Headers` is written for clients, and not
- * servers, and Deno is a server, meaning that it needs to follow the patterns
- * expected for servers, of which a `set-cookie` header is expected for each
- * unique cookie key, but duplicate cookie keys should not exist. */
-  function dataSet(
-    data,
-    key,
-    value,
-  ) {
-    for (let i = 0; i < data.length; i++) {
-      const [dataKey] = data[i];
-      if (dataKey === key) {
-        // there could be multiple set-cookie headers, but all others are unique
-        if (key === "set-cookie") {
-          const [, dataValue] = data[i];
-          const [dataCookieKey] = dataValue.split("=");
-          const [cookieKey] = value.split("=");
-          if (cookieKey === dataCookieKey) {
-            data[i][1] = value;
-            return;
-          }
-        } else {
-          data[i][1] = value;
-          return;
-        }
-      }
+    // 3.
+    if (headers[_guard] == "immutable") {
+      throw new TypeError("Headers are immutable.");
     }
-    data.push([key, value]);
-  }
 
-  function dataDelete(data, key) {
-    let i = 0;
-    while (i < data.length) {
-      const [dataKey] = data[i];
-      if (dataKey === key) {
-        data.splice(i, 1);
-      } else {
-        i++;
+    // 7.
+    const list = headers[_headerList];
+    const lowercaseName = byteLowerCase(name);
+    for (let i = 0; i < list.length; i++) {
+      if (byteLowerCase(list[i][0]) === lowercaseName) {
+        name = list[i][0];
+        break;
       }
     }
+    list.push([name, value]);
   }
 
-  function dataHas(data, key) {
-    for (const [dataKey] of data) {
-      if (dataKey === key) {
-        return true;
-      }
+  /**
+   * @param {HeaderList} list
+   * @param {string} name
+   */
+  function getHeader(list, name) {
+    const lowercaseName = byteLowerCase(name);
+    const entries = list.filter((entry) =>
+      byteLowerCase(entry[0]) === lowercaseName
+    ).map((entry) => entry[1]);
+    if (entries.length === 0) {
+      return null;
+    } else {
+      return entries.join("\x2C\x20");
     }
-    return false;
   }
 
-  // ref: https://fetch.spec.whatwg.org/#dom-headers
-  class HeadersBase {
-    constructor(init) {
-      if (init === null) {
-        throw new TypeError(
-          "Failed to construct 'Headers'; The provided value was not valid",
-        );
-      } else if (isHeaders(init)) {
-        this[headersData] = [...init];
-      } else {
-        this[headersData] = [];
-        if (Array.isArray(init)) {
-          for (const tuple of init) {
-            // If header does not contain exactly two items,
-            // then throw a TypeError.
-            // ref: https://fetch.spec.whatwg.org/#concept-headers-fill
-            requiredArguments(
-              "Headers.constructor tuple array argument",
-              tuple.length,
-              2,
-            );
-
-            this.append(tuple[0], tuple[1]);
-          }
-        } else if (init) {
-          for (const [rawName, rawValue] of Object.entries(init)) {
-            this.append(rawName, rawValue);
+  class Headers {
+    /** @type {HeaderList} */
+    [_headerList] = [];
+    /** @type {"immutable"|  "request"|  "request-no-cors"|  "response" | "none"} */
+    [_guard];
+
+    get [_iterableHeaders]() {
+      const list = this[_headerList];
+
+      const headers = [];
+      const headerNamesSet = new Set();
+      for (const entry of list) {
+        headerNamesSet.add(byteLowerCase(entry[0]));
+      }
+      const names = [...headerNamesSet].sort();
+      for (const name of names) {
+        // The following if statement, and if block of the following statement
+        // are not spec compliant. `set-cookie` is the only header that can not
+        // be concatentated, so must be given to the user as multiple headers.
+        // The else block of the if statement is spec compliant again.
+        if (name == "set-cookie") {
+          const setCookie = list.filter((entry) =>
+            byteLowerCase(entry[0]) === "set-cookie"
+          );
+          if (setCookie.length === 0) throw new TypeError("Unreachable");
+          for (const entry of setCookie) {
+            headers.push([name, entry[1]]);
           }
+        } else {
+          const value = getHeader(list, name);
+          if (value === null) throw new TypeError("Unreachable");
+          headers.push([name, value]);
         }
       }
+      return headers;
     }
 
-    [Symbol.for("Deno.customInspect")]() {
-      let length = this[headersData].length;
-      let output = "";
-      for (const [key, value] of this[headersData]) {
-        const prefix = length === this[headersData].length ? " " : "";
-        const postfix = length === 1 ? " " : ", ";
-        output = output + `${prefix}${key}: ${value}${postfix}`;
-        length--;
+    /** @param {HeadersInit} [init] */
+    constructor(init = undefined) {
+      const prefix = "Failed to construct 'Event'";
+      if (init !== undefined) {
+        init = webidl.converters["HeadersInit"](init, {
+          prefix,
+          context: "Argument 1",
+        });
+      }
+
+      this[webidl.brand] = webidl.brand;
+      this[_guard] = "none";
+      if (init !== undefined) {
+        fillHeaders(this, init);
       }
-      return `Headers {${output}}`;
     }
 
-    // ref: https://fetch.spec.whatwg.org/#concept-headers-append
+    /**
+     * @param {string} name 
+     * @param {string} value 
+     */
     append(name, value) {
-      requiredArguments("Headers.append", arguments.length, 2);
-      const [newname, newvalue] = normalizeParams(name, value);
-      validateName(newname);
-      validateValue(newvalue);
-      dataAppend(this[headersData], newname, newvalue);
+      webidl.assertBranded(this, Headers);
+      const prefix = "Failed to execute 'append' on 'Headers'";
+      webidl.requiredArguments(arguments.length, 2, { prefix });
+      name = webidl.converters["ByteString"](name, {
+        prefix,
+        context: "Argument 1",
+      });
+      value = webidl.converters["ByteString"](value, {
+        prefix,
+        context: "Argument 2",
+      });
+      appendHeader(this, name, value);
     }
 
+    /**
+     * @param {string} name 
+     */
     delete(name) {
-      requiredArguments("Headers.delete", arguments.length, 1);
-      const [newname] = normalizeParams(name);
-      validateName(newname);
-      dataDelete(this[headersData], newname);
+      const prefix = "Failed to execute 'delete' on 'Headers'";
+      webidl.requiredArguments(arguments.length, 1, { prefix });
+      name = webidl.converters["ByteString"](name, {
+        prefix,
+        context: "Argument 1",
+      });
+
+      if (!HTTP_TOKEN_CODE_POINT_RE.test(name)) {
+        throw new TypeError("Header name is not valid.");
+      }
+      if (this[_guard] == "immutable") {
+        throw new TypeError("Headers are immutable.");
+      }
+
+      const list = this[_headerList];
+      const lowercaseName = byteLowerCase(name);
+      for (let i = 0; i < list.length; i++) {
+        if (byteLowerCase(list[i][0]) === lowercaseName) {
+          list.splice(i, 1);
+          i--;
+        }
+      }
     }
 
+    /**
+     * @param {string} name 
+     */
     get(name) {
-      requiredArguments("Headers.get", arguments.length, 1);
-      const [newname] = normalizeParams(name);
-      validateName(newname);
-      return dataGet(this[headersData], newname) ?? null;
+      const prefix = "Failed to execute 'get' on 'Headers'";
+      webidl.requiredArguments(arguments.length, 1, { prefix });
+      name = webidl.converters["ByteString"](name, {
+        prefix,
+        context: "Argument 1",
+      });
+
+      if (!HTTP_TOKEN_CODE_POINT_RE.test(name)) {
+        throw new TypeError("Header name is not valid.");
+      }
+
+      const list = this[_headerList];
+      return getHeader(list, name);
     }
 
+    /**
+     * @param {string} name 
+     */
     has(name) {
-      requiredArguments("Headers.has", arguments.length, 1);
-      const [newname] = normalizeParams(name);
-      validateName(newname);
-      return dataHas(this[headersData], newname);
+      const prefix = "Failed to execute 'has' on 'Headers'";
+      webidl.requiredArguments(arguments.length, 1, { prefix });
+      name = webidl.converters["ByteString"](name, {
+        prefix,
+        context: "Argument 1",
+      });
+
+      if (!HTTP_TOKEN_CODE_POINT_RE.test(name)) {
+        throw new TypeError("Header name is not valid.");
+      }
+
+      const list = this[_headerList];
+      const lowercaseName = byteLowerCase(name);
+      for (let i = 0; i < list.length; i++) {
+        if (byteLowerCase(list[i][0]) === lowercaseName) {
+          return true;
+        }
+      }
+      return false;
     }
 
+    /**
+     * @param {string} name 
+     * @param {string} value 
+     */
     set(name, value) {
-      requiredArguments("Headers.set", arguments.length, 2);
-      const [newName, newValue] = normalizeParams(name, value);
-      validateName(newName);
-      validateValue(newValue);
-      dataSet(this[headersData], newName, newValue);
+      webidl.assertBranded(this, Headers);
+      const prefix = "Failed to execute 'set' on 'Headers'";
+      webidl.requiredArguments(arguments.length, 2, { prefix });
+      name = webidl.converters["ByteString"](name, {
+        prefix,
+        context: "Argument 1",
+      });
+      value = webidl.converters["ByteString"](value, {
+        prefix,
+        context: "Argument 2",
+      });
+
+      value = normalizeHeaderValue(value);
+
+      // 2.
+      if (!HTTP_TOKEN_CODE_POINT_RE.test(name)) {
+        throw new TypeError("Header name is not valid.");
+      }
+      if (
+        value.includes("\x00") || value.includes("\x0A") ||
+        value.includes("\x0D")
+      ) {
+        throw new TypeError("Header value is not valid.");
+      }
+
+      if (this[_guard] == "immutable") {
+        throw new TypeError("Headers are immutable.");
+      }
+
+      const list = this[_headerList];
+      const lowercaseName = byteLowerCase(name);
+      let added = false;
+      for (let i = 0; i < list.length; i++) {
+        if (byteLowerCase(list[i][0]) === lowercaseName) {
+          if (!added) {
+            list[i][1] = value;
+            added = true;
+          } else {
+            list.splice(i, 1);
+            i--;
+          }
+        }
+      }
+      if (!added) {
+        list.push([name, value]);
+      }
+    }
+
+    [Symbol.for("Deno.customInspect")](inspect) {
+      const headers = {};
+      for (const header of this) {
+        headers[header[0]] = header[1];
+      }
+      return `Headers ${inspect(headers)}`;
     }
 
     get [Symbol.toStringTag]() {
@@ -249,7 +329,35 @@
     }
   }
 
-  class Headers extends DomIterableMixin(HeadersBase, headersData) {}
+  webidl.mixinPairIterable("Headers", Headers, _iterableHeaders, 0, 1);
+
+  webidl.converters["sequence<ByteString>"] = webidl
+    .createSequenceConverter(webidl.converters["ByteString"]);
+  webidl.converters["sequence<sequence<ByteString>>"] = webidl
+    .createSequenceConverter(webidl.converters["sequence<ByteString>"]);
+  webidl.converters["record<ByteString, ByteString>"] = webidl
+    .createRecordConverter(
+      webidl.converters["ByteString"],
+      webidl.converters["ByteString"],
+    );
+  webidl.converters["HeadersInit"] = (V, opts) => {
+    // Union for (sequence<sequence<ByteString>> or record<ByteString, ByteString>)
+    if (typeof V === "object" && V !== null) {
+      if (V[Symbol.iterator] !== undefined) {
+        return webidl.converters["sequence<sequence<ByteString>>"](V, opts);
+      }
+      return webidl.converters["record<ByteString, ByteString>"](V, opts);
+    }
+    throw webidl.makeException(
+      TypeError,
+      "The provided value is not of type '(sequence<sequence<ByteString>> or record<ByteString, ByteString>)'",
+      opts,
+    );
+  };
+  webidl.converters["Headers"] = webidl.createInterfaceConverter(
+    "Headers",
+    Headers,
+  );
 
   window.__bootstrap.headers = {
     Headers,