infra.bs

<pre class=metadata>
Group: WHATWG
H1: Infra
Shortname: infra
Text Macro: TWITTER infrastandard
Text Macro: LATESTRD 2024-01
Abstract: The Infra Standard aims to define the fundamental concepts upon which standards are built.
Translation: ja https://triple-underscore.github.io/infra-ja.html
Required IDs: tracking-vector
</pre>

<pre class=anchors>
urlPrefix: https://tc39.github.io/ecma262/#; spec: ECMA-262;
    type: dfn
        text: %JSON.parse%; url: sec-json.parse
        text: %JSON.stringify%; url: sec-json.stringify
        text: List; url: sec-list-and-record-specification-type
        text: The String Type; url: sec-ecmascript-language-types-string-type
        text: realm; url: realm
    type: method; for: Array; text: sort(); url: sec-array.prototype.sort
    type: abstract-op;
        text: ArrayCreate; url: sec-arraycreate
        text: Call; url: sec-call
        text: CreateDataPropertyOrThrow; url: sec-createdatapropertyorthrow
        text: Get; url: sec-get-o-p
        text: IsArray; url: sec-isarray
        text: OrdinaryObjectCreate; url: sec-ordinaryobjectcreate
        text: ToLength; url: sec-tolength
        text: ToString; url: sec-tostring
        text: Type; url: sec-ecmascript-data-types-and-values
</pre>

<style>
/* Used for normative exemplars of how to write algorithms, as distinct from .example */
.exemplary-prose {
  margin-left: 2em;
}
</style>


<h2 id=goals class=no-num>Goals</h2>

<ul>
 <li><p>Deduplicate boilerplate in standards.

 <li><p>Align standards on conventions, terminology, and data structures.

 <li><p>Be a place for concepts used by multiple standards without a good home.

 <li><p>Help write clear and readable algorithmic prose by clarifying otherwise ambiguous concepts.
</ul>

<p>Suggestions for more goals welcome.</p>


<h2 id=usage>Usage</h2>

<p>To make use of this standard in a document titled <var>X</var>, use:

<p><samp><var>X</var> depends on <cite>Infra</cite>. [[!Infra]]</samp>
<!--                                                 Yo Dawg -->

<p>Additionally, cross-referencing all terminology is strongly encouraged to avoid ambiguity.


<h2 id=conventions>Conventions</h2>

<h3 id=conformance>Conformance</h3>

<p>All assertions, diagrams, examples, and notes are non-normative, as are all sections explicitly
marked non-normative. Everything else is normative.

<p>The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT",
"RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" are to be interpreted as described in
RFC 2119. [[!RFC2119]]

<p>These keywords have equivalent meaning when written in lowercase and cannot appear in
non-normative content.

<p class=note>This is a <a>willful violation</a> of RFC 8174, motivated by legibility and a desire
to preserve long-standing practice in many non-IETF-published pre-RFC 8174 documents. [[RFC8174]]

<p>All of the above is applicable to both this standard and any document that uses this standard.
Documents using this standard are encouraged to limit themselves to "must", "must not", "should",
and "may", and to use these in their lowercase form as that is generally considered to be more
readable.

<p>For non-normative content "strongly encouraged", "strongly discouraged", "encouraged",
"discouraged", "can", "cannot", "could", "could not", "might", and "might not" can be used instead.


<h3 id=other-specs>Compliance with other specifications</h3>

<p>In general, specifications interact with and rely on a wide variety of other specifications. In
certain circumstances, unfortunately, conflicting needs require a specification to violate the
requirements of other specifications. When this occurs, a document using the Infra Standard should
denote such transgressions as a <dfn export>willful violation</dfn>, and note the reason for that
violation.

<p class=example id=example-willful-violation>The previous section, [[#conformance]], documents a
<a>willful violation</a> of RFC 8174 committed by <cite>Infra</cite>.


<h3 id=terminology>Terminology</h3>

<p>The word "or", in cases where both inclusive "or" and exclusive "or" are possible (e.g., "if
either width or height is zero"), means an inclusive "or" (implying "or both"), unless it is called
out as being exclusive (with "but not both").

<hr>

<p>A <dfn export>user agent</dfn> is any software entity that acts on behalf
of a user, for example by retrieving and rendering web content and facilitating end user interaction
with it. In specifications using the Infra Standard, the user agent is generally an instance of the client software
that implements the specification. The client software itself is known as an <dfn export>implementation</dfn>.
A person can use many different [=user agents=] in their day-to-day life, including by configuring an
[=implementation=] to act as several [=user agents=] at once, for example by using multiple profiles
or the implementation's private browsing mode.

<p>If something is said to be <dfn export>implementation-defined</dfn>, the particulars of what is
said to be <a>implementation-defined</a> are up to the <a>implementation</a>. In the absence of such
language, the reverse holds: <a>implementations</a> have to follow the rules laid out in documents using
this standard.

<p class="example" id=example-implementation-defined>Insert U+000A (LF) code points into
<var ignore>input</var> in an <a>implementation-defined</a> manner such that each resulting line has
no more than <var ignore>width</var> code points. For the purposes of this requirement, lines are
delimited by the start of <var ignore>input</var>, the end of <var ignore>input</var>, and
U+000A (LF).


<h3 id=privacy>Privacy concerns</h3>

<p>Some features that are defined in documents using the Infra Standard might trade user convenience
for a measure of user privacy.

<p>In general, due to the internet's architecture, a user can be distinguished from another by the
user's IP address. IP addresses do not perfectly match to a user; as a user moves from device to
device, or from network to network, their IP address will change; similarly, NAT routing, proxy
servers, and shared computers enable packets that appear to all come from a single IP address to
actually map to multiple users. Technologies such as onion routing can be used to further anonymize
requests so that requests from a single user at one node on the internet appear to come from many
disparate parts of the network. [[RFC791]]

<p>However, the IP address used for a user's requests is not the only mechanism by which a user's
requests could be related to each other. Cookies, for example, are designed specifically to enable
this, and are the basis of most of the web's session features that enable you to log into a site
with which you have an account. More generally, any kind of cache mechanism or shared state,
including but not limited to HSTS, the HTTP cache, grouping of connections, storage APIs, can and
ought to be expected to be abused. [[COOKIES]] [[RFC6797]] [[STORAGE]]

<p>There are other mechanisms that are more subtle. Certain characteristics of a user's system can
be used to distinguish groups of users from each other. By collecting enough such information, an
individual user's browser's "digital fingerprint" can be computed, which can be better than an IP
address in ascertaining which requests are from the same user.

<p>Grouping requests in this manner, especially across multiple sites, can be used for malevolent
purposes, e.g., governments combining information such as the person's home address (determined from
the addresses they use when getting driving directions on one site) with their apparent political
affiliations (determined by examining the forum sites that they participate in) to determine whether
the person should be prevented from voting in an election.

<p>Since the malevolent purposes can be remarkably evil, user agent implementors and specification
authors are strongly encouraged to minimize leaking information that could be used to fingerprint or
track a user.

<p>Unfortunately, as the first paragraph in this section implies, sometimes there is great benefit
to be derived from exposing APIs that can also be abused for fingerprinting and tracking purposes,
so it's not as easy as blocking all possible leaks. For instance, the ability to log into a site to
post under a specific identity requires that the user's requests be identifiable as all being from
the same user, more or less by definition. More subtly, though, information such as how wide text
is, which is necessary for many effects that involve drawing text onto a canvas (e.g., any effect
that involves drawing a border around the text) also leaks information that can be used to group a
user's requests. (In this case, by potentially exposing, via a brute force search, which fonts a
user has installed, information which can vary considerably from user to user.)

<p tracking-vector>Features that are defined in documents using the Infra Standard that can be used
as a <dfn export>tracking vector</dfn> are marked as this paragraph is.

<p>Other features in the platform can be used for the same purpose, including, but not limited to:

<ul>
 <li>The exact list of which features a user agents supports.
 <li>The maximum allowed stack depth for recursion in script.
 <li>Features that describe the user's environment.
 <li>The user's time zone.
 <li>HTTP request headers.
</ul>


<h2 id=algorithms>Algorithms</h2>

<h3 id=algorithm-conformance>Conformance</h3>

<p>Algorithms, and requirements phrased in the imperative as part of algorithms (such as "strip any
leading spaces" or "return false") are to be interpreted with the meaning of the keyword (e.g.,
"must") used in introducing the algorithm or step. If no such keyword is used, must is implied.

<div class=example id=example-algorithms>
 <p>For example, were the spec to say:</p>

 <div class=exemplary-prose>
  <p class=allow-2119>To <dfn ignore>eat an orange</dfn>, the user must:

  <ol class=brief>
   <li>Peel the orange.
   <li>Separate each slice of the orange.
   <li>Eat the orange slices.
  </ol>
 </div>

 <p>it would be equivalent to the following:</p>

 <div class=exemplary-prose>
  <p>To <dfn ignore>eat an orange</dfn>:

  <ol class=brief>
   <li class=allow-2119>The user must peel the orange.
   <li class=allow-2119>The user must separate each slice of the orange.
   <li class=allow-2119>The user must eat the orange slices.
  </ol>
 </div>

 <p class=allow-2119>Here the key word is "must".</p>

 <p class=allow-2119>Modifying the above example, if the algorithm was introduced only with "To eat
 an orange:", it would still have the same meaning, as "must" is implied.
</div>

<p>Conformance requirements phrased as algorithms or specific steps may be implemented in any
manner, so long as the end result is equivalent. (In particular, the algorithms are intended to be
easy to follow, and not intended to be performant.)

<p class=note>Performance is tricky to get correct as it is influenced by user perception, computer
architectures, and different types of input that can change over time in how common they are. For
instance, a JavaScript engine likely has many different code paths for what is standardized as a
single algorithm, in order to optimize for speed or memory consumption. Standardizing all those code
paths would be an insurmountable task and not productive as they would not stand the test of time
as well as the single algorithm would. Therefore performance is best left as a field to compete
over.


<h3 id=algorithm-limits>Avoid limits on algorithm inputs</h3>

<p>A document using the Infra Standard generally should not enforce specific limits on algorithm
inputs with regards to their size, resource usage, or equivalent. This allows for competition among
user agents and avoids constraining the potential computing needs of the future.

<p tracking-vector>Nevertheless, user agents may impose <a>implementation-defined</a> limits on
otherwise unconstrained inputs. E.g., to prevent denial of service attacks, to guard against running
out of memory, or to work around platform-specific limitations.

<p class=note>Global resource limits can be used as side channels through a variant on a resource
exhaustion attack, whereby the attacker can observe whether a victim application reaches the global
limit. Limits could also be used to fingerprint the user agent, but only if they make the user agent
more unique in some manner, e.g., if they are specific to the underlying hardware.

<p class=example id=example-algorithm-limits>An API that allows creating an in-memory bitmap might
be specified to allow any dimensions, or any dimensions up to some large limit like JavaScript's
<code>Number.MAX_SAFE_INTEGER</code>. However, implementations can choose to impose some
<a>implementation-defined</a> (and thus not specified) limit on the dimensions, instead of
attempting to allocate huge amounts of memory.

<p class=example id=example-algorithm-limits-language>A programming language might not have a
maximum call stack size specified. However, implementations could choose to impose one for practical
reasons.

<p>As code can end up depending on a particular limit, it can be useful to define a limit for
interoperability. Sometimes, embracing that is not problematic for the future, and can make the code
run in more user agents.

<p>It can also be useful to constrain an <a>implementation-defined</a> limit with a lower limit.
I.e., ensuring all implementations can handle inputs of a given minimum size.


<h3 id=algorithm-declaration>Declaration</h3>

<p>Algorithm names are usually verb phrases, but sometimes are given names that emphasize their
standalone existence, so that standards and readers can refer to the algorithm more idiomatically.

<p class=example id=example-algorithm-declaration-names>Some algorithm names in the latter category
include "attribute change steps", "internal module script graph fetching procedure", and "overload
resolution algorithm".

<p>Declare algorithms by stating their name, parameters, and return type, in the following form:

<p class=exemplary-prose>To <dfn ignore>[algorithm name]</dfn>, given a [type1]
<var ignore>[parameter1]</var>, a [type2] <var ignore>[parameter2]</var>, &hellip;, perform the
following steps. They return a [return type].</p>

<p>(For non-verb phrase algorithm names, use "To perform the
<dfn ignore>[algorithm name]</dfn>&hellip;". See also [[#algorithm-params]] for more complicated
parameter-declaration forms.)

<p class=example id=example-algorithm-declaration>To <dfn ignore>parse an awesome format</dfn> given
a [=byte sequence=] <var ignore>bytes</var>, perform the following steps. They return a
[=string=] or null.

<p>Algorithms which do not return a value use a shorter form. This same shorter form can be used even
for algorithms that do return a value if the return type is relatively easy to infer from the
algorithm steps:

<p class=exemplary-prose>To <dfn ignore>[algorithm name]</dfn>, given a [type1]
<var ignore>[parameter1]</var>, a [type2] <var ignore>[parameter2]</var>, &hellip;:</p>

<p class=example id=example-algorithm-declaration-no-return>To
<dfn ignore>parse an awesome format</dfn> given a [=byte sequence=] <var ignore>bytes</var>:

<p>Very short algorithms can be declared and specified using a single sentence:

<p class=example id=example-algorithm-declaration-short>To <dfn ignore>parse an awesome format</dfn>
given a [=byte sequence=] <var ignore>bytes</var>, return the result of
<a lt="ASCII uppercase">ASCII uppercasing</a> the <a lt="isomorphic decode">isomorphic decoding</a>
of <var ignore>bytes</var>.

<p>Types should be included in algorithm declarations, but may be omitted if the parameter name is
clear enough, or if they are otherwise clear from context. (For example, because the algorithm is
a simple wrapper around another one.)

<p class=example id=example-algorithm-declaration-no-types>To
<dfn ignore>load a classic script</dfn> given <var>url</var>, return the result of performing the
internal script-loading algorithm given <var>url</var> and "<code>classic</code>".


<h3 id=algorithm-params>Parameters</h3>

<p>Algorithm parameters are usually listed sequentially, in the fashion described in
[[#algorithm-declaration]]. However, there are some more complicated cases.</p>

<p>Algorithm parameters can be optional, in which case the algorithm declaration must list them as
such, and list them after any non-optional parameters. They can either be given a default value, or
the algorithm body can check whether or not the argument was given. Concretely, use the following
forms:

<p class=exemplary-prose>&hellip; an optional [type] <var ignore>[parameter]</var> &hellip;

<p class=exemplary-prose>&hellip; an optional [type] <var ignore>[parameter]</var> (default [default
value]) &hellip;

<p>Optional <a>boolean</a> parameters must have a default value specified, and that default must be
false.

<div class=example id=example-algorithm-optional-positional-params>
 <p class=allow-2119>To <dfn ignore id=example-navigate-algo-positional>navigate</dfn> to a
 resource <var ignore>resource</var>, with an optional string <var ignore>navigationType</var> and
 an optional boolean <var ignore>exceptionsEnabled</var> (default false):

 <ol class=brief>
  <li>&hellip;
  <li>If <var ignore>navigationType</var> was given, then do something with
  <var ignore>navigationType</var>.
  <li>&hellip;
 </ol>
</div>

<p>To call algorithms with such optional positional parameters, the optional argument values can be
omitted, but only the trailing ones.

<div class=example id=example-algorithm-optional-positional-params-calling>
 <p>Call sites to the previous example's algorithm would look like one of:

 <ul class=brief>
  <li><a href=#example-navigate-algo-positional>Navigate</a> to <var ignore>resource</var>.

  <li><a href=#example-navigate-algo-positional>Navigate</a> to <var ignore>resource</var> with
  "<code>form submission</code>".

  <li><a href=#example-navigate-algo-positional>Navigate</a> to <var ignore>resource</var> with
  "<code>form submission</code>" and true.
 </ul>

 <p>But, there would be no way to supply a non-default value for the third
 (<var ignore>exceptionsEnabled</var>) argument, while leaving the second
 (<var ignore>navigationType</var>) argument as not-given. Additionally, the last of these calls is
 fairly unclear for readers, as the fact that "true" means "exceptions enabled" requires going back
 to the algorithm's declaration and counting parameters. Read on for how to fix these issues!
</div>

<p>Optional named parameters, instead of positional ones, can be used to increase clarity and
flexibility at the call site. Such parameters are marked up as both variables and definitions, and
linked to from their call sites.

<div class=example id=example-algorithm-optional-named-params>
 <p class=allow-2119>To <dfn ignore id=example-navigate-algo-named>navigate</dfn> to a
 resource <var ignore>resource</var>, with an optional string
 <dfn ignore id=example-navigate-algo-navigationType><var ignore>navigationType</var></dfn> and an
 optional boolean
 <dfn ignore id=example-navigate-algo-exceptionsEnabled><var ignore>exceptionsEnabled</var></dfn>
 (default false):

 <ol class=brief>
  <li>&hellip;
  <li>If <var ignore>navigationType</var> was given, then do something with
  <var ignore>navigationType</var>.
  <li>&hellip;
 </ol>

 <p>Call sites would then look like one of:

 <ul class=brief>
  <li><a href=#example-navigate-algo-named>Navigate</a> to <var ignore>resource</var>.

  <li><a href=#example-navigate-algo-named>Navigate</a> to <var ignore>resource</var> with
  <a href=#example-navigate-algo-navigationType><i>navigationType</i></a> set to
  "<code>form-submission</code>".

  <li><a href=#example-navigate-algo-named>Navigate</a> to <var ignore>resource</var> with
  <a href=#example-navigate-algo-exceptionsEnabled><i>exceptionsEnabled</i></a> set to true.

  <li><a href=#example-navigate-algo-named>Navigate</a> to <var ignore>resource</var> with
  <a href=#example-navigate-algo-navigationType><i>navigationType</i></a> set to
  "<code>form-submission</code>" and
  <a href=#example-navigate-algo-exceptionsEnabled><i>exceptionsEnabled</i></a> set to
  true.
 </ul>
</div>

<p class=note>Note how within the algorithm steps, the argument value is not linked to the parameter
declaration; it remains just a variable reference. Linking to the parameter declaration is done only
at the call sites.

<p>Non-optional named parameters may also be used, using the same convention of marking them up as
both variables and definitions, and linking to them from call sites. This can improve clarity at the
call sites.

<p class="example allow-2119" id=example-algorithm-non-optional-named-params><a>Boolean</a>
parameters are a case where naming the parameter can be significantly clearer than leaving it as
positional, regardless of optionality. See
<a href="https://ariya.io/2011/08/hall-of-api-shame-boolean-trap"><cite>The Pitfalls of Boolean
Trap</cite></a> for discussion of this in the context of programming languages.

<p>Another complementary technique for improving clarity is to package up related values into a
<a>struct</a>, and pass that struct as a parameter. This is especially applicable when the same set
of related values is used as the input to multiple algorithms.


<h3 id=variables>Variables</h3>

<p>A variable is declared with "let" and changed with "set".

<p class=example id=example-variable>Let |list| be a new <a>list</a>.</p>

<div class=example id=example-variable-null>
 <ol>
  <li><p>Let |value| be null.

  <li><p>If |input| is a <a>string</a>, then set |value| to |input|.

  <li><p>Otherwise, set |value| to |input|, <a>UTF-8 decoded</a>.

  <li><p><a>Assert</a>: |value| is a <a>string</a>.
 </ol>
</div>

<p class=example id=example-variable-ternary>Let <var ignore>activationTarget</var> be
<var ignore>target</var> if <var ignore>isActivationEvent</var> is true and <var ignore>target</var> has activation
behavior; otherwise null.

<p>Variables must not be used before they are declared. Variables are
<a href=https://en.wikipedia.org/wiki/Scope_(computer_science)#Block_scope>block scoped</a>.
Variables must not be declared more than once per algorithm.

<p>A multiple assignment syntax can be used to assign multiple variables to the <a>tuple</a>'s
<a for=tuple>items</a>, by surrounding the variable names with parenthesis and separating each
variable name by a comma. The number of variables assigned cannot differ from the number of
<a for=tuple>items</a> in the <a>tuple</a>.

<div class=example id=example-tuple-multiple-assignment>
 <ol>
  <li><p>Let |statusInstance| be the status (200, `<code>OK</code>`).
  <li><p>Let (|status|, |statusMessage|) be |statusInstance|.
 </ol>

 <p>Assigning |status| and |statusMessage| could be written as two separate steps that use an index
 or <a for=tuple>name</a> to access the <a>tuple</a>'s <a for=tuple>items</a>.
</div>


<h3 id=algorithm-control-flow>Control flow</h3>

<p>The control flow of algorithms is such that a requirement to "return" or "throw" terminates the
algorithm the statement was in. "Return" will hand the given value, if any, to its caller. "Throw"
will make the caller automatically rethrow the given value, if any, and thereby terminate the
caller's algorithm. Using prose the caller has the ability to "catch" the exception and perform
another action.


<h3 id=algorithm-conditional-abort>Conditional abort</h3>

<p>Sometimes it is useful to stop performing a series of steps once a condition becomes true.

<p>To do this, state that a given series of steps will <dfn export>abort when</dfn> a specific
<var>condition</var> is reached. This indicates that the specified steps must be evaluated, not
as-written, but by additionally inserting a step before each of them that evaluates
<var>condition</var>, and if <var>condition</var> evaluates to true, skips the remaining steps.

<p>In such algorithms, the subsequent step can be annotated to run <dfn export>if aborted</dfn>, in
which case it must run if any of the preceding steps were skipped due to the <var>condition</var>
of the preceding <a>abort when</a> step evaluated to true.

<div class=example id=example-conditional-abort>
 <p>The following algorithm

 <ol>
  <li><p>Let |result| be an empty <a>list</a>.

  <li>
   <p>Run these steps, but <a>abort when</a> the user clicks the "Cancel" button:

   <ol>
    <li><p>Compute the first million digits of <var>π</var>, and <a for=list>append</a> the result
    to |result|.

    <li><p>Compute the first million digits of |e|, and <a for=list>append</a> the result to
    |result|.

    <li><p>Compute the first million digits of <var>φ</var>, and <a for=list>append</a> the result
    to |result|.
   </ol>
  </li>

  <li><p><a>If aborted</a>, <a for=list>append</a> "<code>Didn't finish!</code>" to |result|.
 </ol>

 <p>is equivalent to the more verbose formulation</p>

 <ol>
  <li><p>Let |result| be an empty <a>list</a>.

  <li>
   <p>If the user has not clicked the "Cancel" button, then:

   <ol>
    <li><p>Compute the first million digits of <var>π</var>, and <a for=list>append</a> the result
    to |result|.

    <li>
     <p>If the user has not clicked the "Cancel" button, then:

     <ol>
      <li><p>Compute the first million digits of |e|, and <a for=list>append</a> the result to
      |result|.

      <li><p>If the user has not clicked the "Cancel" button, then compute the first million digits
      of <var>φ</var>, and <a for=list>append</a> the result to |result|.
     </ol>
   </ol>

  <li><p>If the user clicked the "Cancel" button, then <a for=list>append</a>
  "<code>Didn't finish!</code>" to |result|.
 </ol>
</div>

<p class=note>Whenever this construct is used, implementations are allowed to evaluate
<var>condition</var> during the specified steps rather than before and after each step, as long as
the end result is indistinguishable. For instance, as long as |result| in the above example is not
mutated during a compute operation, the user agent could stop the computation.


<h3 id=algorithm-conditional-statements>Conditional statements</h3>

<p>Algorithms with conditional statements should use the keywords "if", "then", and "otherwise".

<div class=example id=example-conditional-statement>
 <ol>
  <li><p>Let |value| be null.

  <li><p>If |input| is a <a>string</a>, then set |value| to |input|.

  <li><p>Return |value|.
 </ol>
</div>

Once the keyword "otherwise" is used, the keyword "then" is omitted.

<div class=example id=example-conditional-statement-no-then-1>
 <ol>
  <li><p>Let |value| be null.

  <li><p>If |input| is a <a>string</a>, then set |value| to |input|.

  <li><p>Otherwise, set |value| to failure.

  <li><p>Return |value|.
 </ol>
</div>

<div class=example id=example-conditional-statement-no-then-2>
 <ol>
  <li><p>Let |value| be null.

  <li><p>If |input| is a <a>string</a>, then set |value| to |input|.

  <li><p>Otherwise, if |input| is a <a>list</a> of <a>strings</a>, set |value| to |input|[0].

  <li><p>Otherwise, throw a {{TypeError}}.

  <li><p>Return |value|.
 </ol>
</div>


<h3 id=algorithm-iteration>Iteration</h3>

<p>There's a variety of ways to repeat a set of steps until a condition is reached.

<p class=note>The Infra Standard is not (yet) exhaustive on this; please file an issue if you need
something.

<dl>
 <dt>For each
 <dd><p>As defined for <a for=list lt="for each">lists</a> (and derivatives) and
 <a for=map lt="for each">maps</a>.

 <dt><dfn export for=iteration lt=while>While</dfn>
 <dd>
  <p>An instruction to repeat a set of steps as long as a condition is met.

  <div class=example id=example-while>
   <p>While |condition| is "<code>met</code>":

   <ol>
    <li><p>&hellip;
   </ol>
  </div>
</dl>

<p>An iteration's flow can be controlled via requirements to
<dfn export for=iteration>continue</dfn> or <dfn export for=iteration>break</dfn>.
<a for=iteration>Continue</a> will skip over any remaining steps in an iteration, proceeding to the
next item. If no further items remain, the iteration will stop. <a for=iteration>Break</a> will skip
over any remaining steps in an iteration, and skip over any remaining items as well, stopping the
iteration.

<div class=example id=example-break-continue>
 <p>Let |example| be the <a>list</a> « 1, 2, 3, 4 ». The following prose would perform |operation|
 upon 1, then 2, then 3, then 4:

 <ol>
  <li>
   <p><a for=list>For each</a> |item| of |example|:
   <ol>
    <li>Perform |operation| on |item|.
   </ol>
  </li>
 </ol>

 <p>The following prose would perform |operation| upon 1, then 2, then 4. 3 would be skipped.

 <ol>
  <li>
   <p><a for=list>For each</a> |item| of |example|:
   <ol>
    <li>If |item| is 3, then <a for=iteration>continue</a>.
    <li>Perform |operation| on |item|.
   </ol>
  </li>
 </ol>

 <p>The following prose would perform |operation| upon 1, then 2. 3 and 4 would be skipped.

 <ol>
  <li>
   <p><a for=list>For each</a> |item| of |example|:
   <ol>
    <li>If |item| is 3, then <a for=iteration>break</a>.
    <li>Perform |operation| on |item|.
   </ol>
  </li>
 </ol>
</div>


<h3 id=assertions>Assertions</h3>

<p>To improve readability, it can sometimes help to add assertions to algorithms, stating
invariants. To do this, write "<dfn export>Assert</dfn>:", followed by a statement that must be
true. If the statement ends up being false that indicates an issue with the document using the Infra
Standard that should be reported and addressed.

<p class=note>Since the statement can only ever be true, it has no implications for implementations.

<div class=example id=example-assert>
 <ol>
  <li><p>Let |x| be "<code>Aperture Science</code>".
  <li><p><a>Assert</a>: |x| is "<code>Aperture Science</code>".
</div>


<h2 id=primitive-data-types>Primitive data types</h2>

<h3 id=nulls>Nulls</h3>

<p>The value null is used to indicate the lack of a value. It can be used interchangeably with the
JavaScript <b>null</b> value. [[!ECMA-262]]

<p class=example id=example-null>Let <var ignore>element</var> be null.

<p class=example id=example-null-return>If <var>input</var> is the empty string, then return null.


<h3 id=booleans>Booleans</h3>

<p>A <dfn export>boolean</dfn> is either true or false.

<p class=example id=example-boolean>Let <var ignore>elementSeen</var> be false.


<h3 id=bytes>Bytes</h3>

<p>A <dfn export>byte</dfn> is a sequence of eight bits and is represented as "<code>0x</code>"
followed by two <a>ASCII upper hex digits</a>, in the range 0x00 to 0xFF, inclusive. A <a>byte</a>'s
<dfn export for=byte>value</dfn> is its underlying number.

<p class=example id=example-byte-value>0x40 is a <a>byte</a> whose <a for=byte>value</a> is 64.

<p>An <dfn export>ASCII byte</dfn> is a <a>byte</a> in the range 0x00 (NUL) to 0x7F (DEL),
inclusive. As illustrated, an <a>ASCII byte</a>, excluding 0x28 and 0x29, may be followed by the
representation outlined in the <a href=https://tools.ietf.org/html/rfc20#section-2>Standard Code</a>
section of <cite>ASCII format for Network Interchange</cite>, between parentheses. [[!RFC20]]

<p>0x28 may be followed by "(left parenthesis)" and 0x29 by "(right parenthesis)".

<p class=example id=example-byte-notation>0x49 (I) when <a>UTF-8 decoded</a> becomes the
<a>code point</a> U+0049 (I).


<h3 id=byte-sequences>Byte sequences</h3>

<p>A <dfn export>byte sequence</dfn> is a sequence of <a>bytes</a>, represented as a space-separated
sequence of bytes. Byte sequences with bytes in the range 0x20 (SP) to 0x7E (~), inclusive, can
alternately be written as a string, but using backticks instead of quotation marks, to avoid
confusion with an actual <a>string</a>.

<div class=example id=example-byte-sequence-notation>
 <p>0x48 0x49 can also be represented as `<code>HI</code>`.

 <p>Headers, such as `<code>Content-Type</code>`, are <a>byte sequences</a>.
</div>

<p class=note>To get a <a>byte sequence</a> out of a <a>string</a>, using <a>UTF-8 encode</a> from
<cite>Encoding</cite> is encouraged. In rare circumstances <a>isomorphic encode</a> might be needed.
[[ENCODING]]

<p>A <a>byte sequence</a>'s <dfn export for="byte sequence">length</dfn> is the number of
<a>bytes</a> it contains.

<p>To <dfn export>byte-lowercase</dfn> a <a>byte sequence</a>, increase each <a>byte</a> it
contains, in the range 0x41 (A) to 0x5A (Z), inclusive, by 0x20.

<p>To <dfn export>byte-uppercase</dfn> a <a>byte sequence</a>, subtract each <a>byte</a> it
contains, in the range 0x61 (a) to 0x7A (z), inclusive, by 0x20.

<p>A <a>byte sequence</a> <var>A</var> is a <dfn export>byte-case-insensitive</dfn> match for a
<a>byte sequence</a> <var>B</var>, if the <a>byte-lowercase</a> of <var>A</var> is the
<a>byte-lowercase</a> of <var>B</var>.

<hr>

<p>A <a>byte sequence</a> <var>potentialPrefix</var> is a
<dfn export for="byte sequence">prefix</dfn> of a <a>byte sequence</a> <var>input</var> if the
following steps return true:

<ol>
 <li><p>Let <var>i</var> be 0.

 <li>
  <p><a>While</a> true:

  <ol>
   <li><p>If <var>i</var> is greater than or equal to <var>potentialPrefix</var>'s
   <a for="byte sequence">length</a>, then return true.

   <li><p>If <var>i</var> is greater than or equal to <var>input</var>'s
   <a for="byte sequence">length</a>, then return false.

   <li><p>Let <var>potentialPrefixByte</var> be the <var>i</var>th <a>byte</a> of
   <var>potentialPrefix</var>.

   <li><p>Let <var>inputByte</var> be the <var>i</var>th <a>byte</a> of <var>input</var>.

   <li><p>Return false if <var>potentialPrefixByte</var> is not <var>inputByte</var>.

   <li><p>Set <var>i</var> to <var>i</var> + 1.
  </ol>
 </li>
</ol>

<p>"<var>input</var> <dfn export for="byte sequence" lt="starts with|start with">starts with</dfn>
<var>potentialPrefix</var>" can be used as a synonym for "<var>potentialPrefix</var> is a
<a for="byte sequence">prefix</a> of <var>input</var>".

<p>A <a>byte sequence</a> <var>a</var> is <dfn export>byte less than</dfn> a <a>byte sequence</a>
<var>b</var> if the following steps return true:

<ol>
 <li><p>If <var>b</var> is a <a for="byte sequence">prefix</a> of <var>a</var>, then return false.

 <li><p>If <var>a</var> is a <a for="byte sequence">prefix</a> of <var>b</var>, then return true.

 <li><p>Let <var>n</var> be the smallest index such that the <var>n</var>th <a>byte</a> of
 <var>a</var> is different from the <var>n</var>th byte of <var>b</var>. (There has to be such an
 index, since neither byte sequence is a prefix of the other.)

 <li><p>If the <var>n</var>th byte of <var>a</var> is less than the <var>n</var>th byte of
 <var>b</var>, then return true.

 <li><p>Return false.
</ol>

<hr>

<p>To <dfn export>isomorphic decode</dfn> a <a>byte sequence</a> <var>input</var>, return a
<a>string</a> whose <a for=string>code point length</a> is equal to <var>input</var>'s
<a for="byte sequence">length</a> and whose <a>code points</a> have the same
<a for="code point">values</a> as the <a for=byte>values</a> of <var>input</var>'s <a>bytes</a>, in
the same order.


<h3 id=code-points>Code points</h3>

<p>A <dfn export lt="code point|character">code point</dfn> is a Unicode code point and is
represented as "U+" followed by four-to-six <a>ASCII upper hex digits</a>, in the range U+0000 to
U+10FFFF, inclusive. A <a>code point</a>'s <dfn export for="code point">value</dfn> is its
underlying number.

<p>A <a>code point</a> may be followed by its name, by its rendered form between parentheses when it
is not U+0028 or U+0029, or by both. Documents using the Infra Standard are encouraged to follow
<a>code points</a> by their name when they cannot be rendered or are U+0028 or U+0029; otherwise,
follow them by their rendered form between parentheses, for legibility.

<p>A <a>code point</a>'s name is defined in <cite>Unicode</cite> and represented in
<a>ASCII uppercase</a>. [[!UNICODE]]

<div class=example id=example-code-point-notation>
 <p>The <a>code point</a> rendered as 🤔 is represented as U+1F914.

 <p>When referring to that <a>code point</a>, we might say "U+1F914 (🤔)", to provide extra context.
 Documents are allowed to use "U+1F914 THINKING FACE (🤔)" as well, though this is somewhat verbose.
</div>

<p class=example id=example-code-point-notation-hard-to-render><a>Code points</a> that are difficult
to render unambigiously, such as U+000A, can be referred to as "U+000A LF". U+0029 can be referred
to as "U+0029 RIGHT PARENTHESIS", because even though it renders, this avoids unmatched parentheses.

<p><a>Code points</a> are sometimes referred to as <a>characters</a> and in certain contexts are
prefixed with "0x" rather than "U+".

<p>A <dfn export>leading surrogate</dfn> is a <a>code point</a> that is in the range U+D800 to
U+DBFF, inclusive.

<p>A <dfn export>trailing surrogate</dfn> is a <a>code point</a> that is in the range U+DC00 to
U+DFFF, inclusive.

<p>A <dfn export>surrogate</dfn> is a <a>leading surrogate</a> or a <a>trailing surrogate</a>.

<p>A <dfn export>scalar value</dfn> is a <a>code point</a> that is not a <a>surrogate</a>.

<p>A <dfn export>noncharacter</dfn> is a <a>code point</a> that is in the range U+FDD0 to U+FDEF,
inclusive, or U+FFFE, U+FFFF, U+1FFFE, U+1FFFF, U+2FFFE, U+2FFFF, U+3FFFE, U+3FFFF, U+4FFFE,
U+4FFFF, U+5FFFE, U+5FFFF, U+6FFFE, U+6FFFF, U+7FFFE, U+7FFFF, U+8FFFE, U+8FFFF, U+9FFFE, U+9FFFF,
U+AFFFE, U+AFFFF, U+BFFFE, U+BFFFF, U+CFFFE, U+CFFFF, U+DFFFE, U+DFFFF, U+EFFFE, U+EFFFF, U+FFFFE,
U+FFFFF, U+10FFFE, or U+10FFFF.

<p>An <dfn export>ASCII code point</dfn> is a <a>code point</a> in the range U+0000 NULL to
U+007F DELETE, inclusive.

<p>An <dfn export lt="ASCII tab or newline|ASCII tabs or newlines">ASCII tab or newline</dfn> is
U+0009 TAB, U+000A LF, or U+000D CR.

<p><dfn export>ASCII whitespace</dfn> is U+0009 TAB, U+000A LF, U+000C FF, U+000D CR, or U+0020
SPACE.

<p class=note>"Whitespace" is a mass noun.

<p>A <dfn export>C0 control</dfn> is a <a>code point</a> in the range U+0000 NULL to
U+001F INFORMATION SEPARATOR ONE, inclusive.

<p>A <dfn export lt="C0 control or space|C0 controls or spaces">C0 control or space</dfn> is a
<a>C0 control</a> or U+0020 SPACE.

<p>A <dfn export>control</dfn> is a <a>C0 control</a> or a <a>code point</a> in the range
U+007F DELETE to U+009F APPLICATION PROGRAM COMMAND, inclusive.

<p>An <dfn export>ASCII digit</dfn> is a <a>code point</a> in the range U+0030 (0) to U+0039 (9),
inclusive.

<p>An <dfn export>ASCII upper hex digit</dfn> is an <a>ASCII digit</a> or a <a>code point</a> in the
range U+0041 (A) to U+0046 (F), inclusive.

<p>An <dfn export>ASCII lower hex digit</dfn> is an <a>ASCII digit</a> or a <a>code point</a> in the
range U+0061 (a) to U+0066 (f), inclusive.

<p>An <dfn export>ASCII hex digit</dfn> is an <a>ASCII upper hex digit</a> or
<a>ASCII lower hex digit</a>.

<p>An <dfn export>ASCII upper alpha</dfn> is a <a>code point</a> in the range U+0041 (A) to
U+005A (Z), inclusive.

<p>An <dfn export>ASCII lower alpha</dfn> is a <a>code point</a> in the range U+0061 (a) to
U+007A (z), inclusive.

<p>An <dfn export>ASCII alpha</dfn> is an <a>ASCII upper alpha</a> or <a>ASCII lower alpha</a>.

<p>An <dfn export>ASCII alphanumeric</dfn> is an <a>ASCII digit</a> or <a>ASCII alpha</a>.


<h3 id=strings>Strings</h3>

<p>A <dfn export lt="string|JavaScript string">string</dfn> is a sequence of unsigned 16-bit
integers, also known as <dfn export lt="code unit">code units</dfn>. A <a>string</a> is also known
as a <a id="javascript-string">JavaScript string</a>. <a>Strings</a> are denoted by double quotes
and monospace font.

<p class=example id=example-string-notation>"<code>Hello, world!</code>" is a string.

<p class=note>This is different from how <cite>Unicode</cite> defines "code unit". In particular it
refers exclusively to how <cite>Unicode</cite> defines it for Unicode 16-bit strings. [[UNICODE]]

<p>A <a>string</a> can also be interpreted as containing <a>code points</a>, per the conversion
defined in <a>The String Type</a> section of the JavaScript specification. [[!ECMA-262]]

<p class=note>This conversion process converts surrogate pairs into their corresponding
<a>scalar value</a> and maps any remaining surrogates to their corresponding <a>code point</a>,
leaving them effectively as-is.

<p class=example id=example-javascript-string-in-code-points>A <a>string</a> consisting of the
<a>code units</a> 0xD83D, 0xDCA9, and 0xD800, when interpreted as containing <a>code points</a>,
would consist of the <a>code points</a> U+1F4A9 and U+D800.

<p>A <a>string</a>'s
<dfn export for="string,JavaScript string,scalar value string" id=string-length oldids=javascript-string-length>length</dfn>
is the number of <a>code units</a> it contains.

<p>A <a>string</a>'s
<dfn export for="string,JavaScript string,scalar value string">code point length</dfn> is the number
of <a>code points</a> it contains.

<p>A <dfn export>scalar value string</dfn> is a <a>string</a> whose <a>code points</a> are all
<a>scalar values</a>.

<p class=note>A <a>scalar value string</a> is useful for any kind of I/O or other kind of operation
where <a>UTF-8 encode</a> comes into play.
<!-- It's also useful if you can imagine the subsystem to be implemented in Rust -->

<p>To <dfn export for="string,JavaScript string" id=javascript-string-convert>convert</dfn> a
<a>string</a> into a <a>scalar value string</a>, replace any <a>surrogates</a> with U+FFFD (�).

<div class=note>
 <p>The replaced surrogates are never part of surrogate pairs, since the process of interpreting the
 string as containing <a>code points</a> will have converted surrogate pairs into
 <a>scalar values</a>.

 <p>A <a>scalar value string</a> can always be used as a <a>string</a> implicitly since every
 <a>scalar value string</a> is a <a>string</a>. On the other hand, a <a>string</a> can only be
 implicitly used as a <a>scalar value string</a> if it is known to not contain <a>surrogates</a>;
 otherwise a <a for=string lt=convert>conversion</a> is to be performed.

 <p>An implementation likely has to perform explicit conversion, depending on how it actually ends
 up representing <a>strings</a> and <a>scalar value strings</a>. It is fairly typical for
 implementations to have multiple implementations of <a>strings</a> alone for performance and memory
 reasons.
</div>

<hr>

<p>A <a>string</a> <var>a</var> <dfn export for=string lt="is|identical to">is</dfn> or is
<a for=string>identical to</a> a <a>string</a> <var>b</var> if it consists of the same sequence of
<a>code units</a>.

<p>Except where otherwise stated, all string comparisons use <a for=string>is</a>.

<p class=note>This type of <a>string</a> comparison was formerly known as a "case-sensitive"
comparison in <cite>HTML</cite>. Strings that compare as <a for=string>identical to</a> one another
are not only sensitive to case variation (such as UPPER and lower case), but also to other code
point encoding choices, such as normalization form or the order of combining marks. Two strings that
are visually or even canonically equivalent according to <cite>Unicode</cite> might still not be
<a for=string>identical to</a> each other. [[HTML]] [[UNICODE]]

<p>A <a>string</a> <var>potentialPrefix</var> is a <dfn export>code unit prefix</dfn> of a
<a>string</a> <var>input</var> if the following steps return true:

<ol>
 <li><p>Let <var>i</var> be 0.

 <li>
  <p><a>While</a> true:

  <ol>
   <li><p>If <var>i</var> is greater than or equal to <var>potentialPrefix</var>'s
   <a for=string>length</a>, then return true.

   <li><p>If <var>i</var> is greater than or equal to <var>input</var>'s <a for=string>length</a>,
   then return false.

   <li><p>Let <var>potentialPrefixCodeUnit</var> be the <var>i</var>th <a>code unit</a> of
   <var>potentialPrefix</var>.

   <li><p>Let <var>inputCodeUnit</var> be the <var>i</var>th <a>code unit</a> of <var>input</var>.

   <li><p>Return false if <var>potentialPrefixCodeUnit</var> is not <var>inputCodeUnit</var>.

   <li><p>Set <var>i</var> to <var>i</var> + 1.
  </ol>
 </li>
</ol>

<p>When it is clear from context that <a>code units</a> are in play, e.g., because one of the
strings is a literal containing only characters that are in the range U+0020 SPACE to U+007E (~),
"<var>input</var> <dfn export for="string">starts with</dfn> <var>potentialPrefix</var>" can be used
as a synonym for "<var>potentialPrefix</var> is a <a>code unit prefix</a> of <var>input</var>".

<p class=example id=code-unit-prefix-example>With unknown values, it is good to be explicit:
<var ignore>targetString</var> is a <a>code unit prefix</a> of <var>userInput</var>. But with a
literal, we can use plainer language: <var>userInput</var> <a for="string">starts with</a>
"<code>!</code>".

<p>A <a>string</a> <var>potentialSuffix</var> is a <dfn export>code unit suffix</dfn> of a
<a>string</a> <var>input</var> if the following steps return true:

<ol>
 <li><p>Let <var>i</var> be 1.

 <li>
  <p><a>While</a> true:

  <ol>
   <li><p>Let <var>potentialSuffixIndex</var> be <var>potentialSuffix</var>'s
   <a for=string>length</a> &minus; <var>i</var>.

   <li><p>Let <var>inputIndex</var> be <var>input</var>'s <a for=string>length</a> &minus;
   <var>i</var>.

   <li><p>If <var>potentialSuffixIndex</var> is less than 0, then return true.

   <li><p>If <var>inputIndex</var> is less than 0, then return false.

   <li><p>Let <var>potentialSuffixCodeUnit</var> be the <var>potentialSuffixIndex</var>th
   <a>code unit</a> of <var>potentialSuffix</var>.

   <li><p>Let <var>inputCodeUnit</var> be the <var>inputIndex</var>th <a>code unit</a> of
   <var>input</var>.

   <li><p>Return false if <var>potentialSuffixCodeUnit</var> is not <var>inputCodeUnit</var>.

   <li><p>Set <var>i</var> to <var>i</var> + 1.
  </ol>
</ol>

<p>When it is clear from context that <a>code units</a> are in play, e.g., because one of the
strings is a literal containing only characters that are in the range U+0020 SPACE to U+007E (~),
"<var>input</var> <dfn export for=string>ends with</dfn> <var>potentialSuffix</var>" can be used as
a synonym for "<var>potentialSuffix</var> is a <a>code unit suffix</a> of <var>input</var>".

<p class=example id=code-unit-suffix-example>With unknown values, it is good to be explicit:
<var ignore>targetString</var> is a <a>code unit suffix</a> of <var>domain</var>. But with a
literal, we can use plainer language: <var>domain</var> <a for=string>ends with</a>
"<code>.</code>".

<hr>

<p>A <a>string</a> <var>a</var> is <dfn export>code unit less than</dfn> a <a>string</a>
<var>b</var> if the following steps return true:

<ol>
 <li><p>If <var>b</var> is a <a>code unit prefix</a> of <var>a</var>, then return false.

 <li><p>If <var>a</var> is a <a>code unit prefix</a> of <var>b</var>, then return true.

 <li><p>Let <var>n</var> be the smallest index such that the <var>n</var>th <a>code unit</a> of
 <var>a</var> is different from the <var>n</var>th code unit of <var>b</var>. (There has to be such
 an index, since neither string is a prefix of the other.)

 <li><p>If the <var>n</var>th code unit of <var>a</var> is less than the <var>n</var>th code unit of
 <var>b</var>, then return true.

 <li><p>Return false.
</ol>

<p class="note">This matches the ordering used by JavaScript's <code>&lt;</code> operator, and its
{{Array/sort()}} method on an array of strings. This ordering compares the 16-bit code units in each
string, producing a highly efficient, consistent, and deterministic sort order. The resulting
ordering will not match any particular alphabet or lexicographic order, particularly for
<a>code points</a> represented by a surrogate pair. [[!ECMA-262]]

<p class="example" id="example-code-unit-less-than">For example, the code point U+FF5E FULLWIDTH
TILDE (～) is obviously less than the code point U+1F600 (😀), but the tilde is composed of a single
code unit 0xFF5E, while the smiley is composed of two code units 0xD83D and 0XDE00, so the smiley is
[=code unit less than=] the tilde.

<hr>

<p>The <dfn export>code unit substring</dfn> from <var>start</var> with length <var>length</var>
within a <a>string</a> <var>string</var> is determined as follows:

<ol>
 <li><p><a>Assert</a>: <var>start</var> and <var>length</var> are nonnegative.</p></li>

 <li><p><a>Assert</a>: <var>start</var> + <var>length</var> is less than or equal to
 <var>string</var>'s <a for=string>length</a>.</p></li>

 <li><p>Let <var>result</var> be the empty string.</p></li>

 <li><p><a for="set">For each</a> <var>i</var> in <a lt="the exclusive range">the range</a> from
 <var>start</var> to <var>start</var> + <var>length</var>, exclusive: append the <var>i</var>th
 <a>code unit</a> of <var>string</var> to <var>result</var>.</p></li>

 <li><p>Return <var>result</var>.</li>
</ol>

<p>The <dfn export lt="code unit substring by positions">code unit substring</dfn> from
<var>start</var> to <var>end</var> within a <a>string</a> <var>string</var> is the <a>code
unit substring</a> from <var>start</var> with length <var>end</var> &minus; <var>start</var> within
<var>string</var>.

<p>The <dfn export lt="code unit substring to the end of the string">code unit substring</dfn> from
<var>start</var> to the end of a <a>string</a> <var>string</var> is the
<a lt="code unit substring by positions">code unit substring</a> from <var>start</var> to
<var>string</var>'s <a for=string>length</a> within <var>string</var>.

<p class="example" id="example-code-unit-substring">The <a>code unit substring</a> from 1 with
length 3 within "<code>Hello world</code>" is "<code>ell</code>". This can also be expressed as the
<a lt="code unit substring by positions">code unit substring</a> from 1 to 4.

<p class="note">The numbers given to these algorithms are best thought of as positions
<em>between</em> <a>code units</a>, not indices of the code units themselves. The substring returned
is then formed by the code units between these positions. That explains why, for example, the
<a lt="code unit substring by positions">code unit substring</a> from 0 to 0 within the empty string
is the empty string, even though there is no code unit at index 0 within the empty string.

<p>The <dfn export>code point substring</dfn> within a <a>string</a> <var>string</var> from
<var>start</var> with length <var>length</var> is determined as follows:

<ol>
 <li><p><a>Assert</a>: <var>start</var> and <var>length</var> are nonnegative.</p></li>

 <li><p><a>Assert</a>: <var>start</var> + <var>length</var> is less than or equal to
 <var>string</var>'s <a for=string>code point length</a>.</p></li>

 <li><p>Let <var>result</var> be the empty string.</p></li>

 <li><p><a for="set">For each</a> <var>i</var> in <a lt="the exclusive range">the range</a> from
 <var>start</var> to <var>start</var> + <var>length</var>, exclusive: append the <var>i</var>th
 <a>code point</a> of <var>string</var> to <var>result</var>.</p></li>

 <li><p>Return <var>result</var>.</li>
</ol>

<p>The <dfn export lt="code point substring by positions">code point substring</dfn> from
<var>start</var> to <var>end</var> within a <a>string</a> <var>string</var> is the
<a>code point substring</a> within <var>string</var> from <var>start</var> with length
<var>end</var> &minus; <var>start</var>.

<p>The <dfn export lt="code point substring to the end of the string">code point substring</dfn>
from <var>start</var> to the end of a <a>string</a> <var>string</var> is the
<a lt="code point substring by positions">code point substring</a> from <var>start</var> to
<var>string</var>'s <a for=string>code point length</a> within <var>string</var>.

<div class="example" id="example-code-unit-vs-point-substring">
 <p>Generally, <a>code unit substring</a> is used when given developer-supplied positions or
 lengths, since that is how string indexing works in JavaScript. See, for example, the methods of
 the {{CharacterData}} class. [[DOM]]

 <p>Otherwise, <a>code point substring</a> is likely to be better. For example, the
 <a>code point substring</a> from 0 with length 1 within "<code>👽</code>" is "<code>👽</code>",
 whereas the <a>code unit substring</a> from 0 with length 1 within "<code>👽</code>" is the
 <a>string</a> containing the single <a>surrogate</a> U+D83B.
</div>

<hr>

<p>To <dfn export>isomorphic encode</dfn> a <a>string</a> <var>input</var>, run these steps:</p>

<ol>
 <li><p><a>Assert</a>: <var>input</var> contains no <a>code points</a> greater than U+00FF.

 <li><p>Return a <a>byte sequence</a> whose <a for="byte sequence">length</a> is equal to
 <var>input</var>'s <a for=string>code point length</a> and whose <a>bytes</a> have the same
 <a for=byte>values</a> as the <a for="code point">values</a> of <var>input</var>'s
 <a>code points</a>, in the same order.
</ol>

<hr>

<p>An <dfn export>ASCII string</dfn> is a <a>string</a> whose <a>code points</a> are all
<a>ASCII code points</a>.

<p>To <dfn export>ASCII lowercase</dfn> a <a>string</a>, replace all <a>ASCII upper alphas</a> in
the <a>string</a> with their corresponding <a>code point</a> in <a>ASCII lower alpha</a>.

<p>To <dfn export>ASCII uppercase</dfn> a <a>string</a>, replace all <a>ASCII lower alphas</a> in
the <a>string</a> with their corresponding <a>code point</a> in <a>ASCII upper alpha</a>.

<p>A <a>string</a> <var>A</var> is an <dfn export>ASCII case-insensitive</dfn> match for a
<a>string</a> <var>B</var>, if the <a>ASCII lowercase</a> of <var>A</var> is the
<a>ASCII lowercase</a> of <var>B</var>.
<!-- TODO: define string equals? -->

<p>To <dfn export>ASCII encode</dfn> a <a>string</a> <var>input</var>, run these steps:

<ol>
 <li><p><a>Assert</a>: <var>input</var> is an <a>ASCII string</a>.

 <p class=note>Note: This precondition ensures that <a>isomorphic encode</a> and
 <a>UTF-8 encode</a> return the same <a>byte sequence</a> for this input.

 <li><p>Return the <a>isomorphic encoding</a> of <var>input</var>.
</ol>

<p>To <dfn export>ASCII decode</dfn> a <a>byte sequence</a> <var>input</var>, run these steps:

<ol>
 <li><p><a>Assert</a>: All bytes in <var>input</var> are <a>ASCII bytes</a>.

 <p class=note>Note: This precondition ensures that <a>isomorphic decode</a> and
 <a>UTF-8 decode</a> return the same <a>string</a> for this input.

 <li><p>Return the <a>isomorphic decoding</a> of <var>input</var>.
</ol>


<hr>

<p>To <dfn export>strip newlines</dfn> from a <a>string</a>, remove any U+000A LF and U+000D CR
<a>code points</a> from the <a>string</a>.

<p>To <dfn export>normalize newlines</dfn> in a <a>string</a>, replace every U+000D CR U+000A LF
<a>code point</a> pair with a single U+000A LF <a>code point</a>, and then replace every remaining
U+000D CR <a>code point</a> with a U+000A LF <a>code point</a>.

<p>To <dfn export>strip leading and trailing ASCII whitespace</dfn> from a <a>string</a>, remove all
<a>ASCII whitespace</a> that are at the start or the end of the <a>string</a>.

<p>To <dfn export>strip and collapse ASCII whitespace</dfn> in a <a>string</a>, replace any sequence
of one or more consecutive <a>code points</a> that are <a>ASCII whitespace</a> in the <a>string</a>
with a single U+0020 SPACE <a>code point</a>, and then remove any leading and trailing
<a>ASCII whitespace</a> from that string.

<hr>

<p>To <dfn export lt="collect a sequence of code points|collecting a sequence of code
points">collect a sequence of <a>code points</a></dfn> meeting a condition <var>condition</var> from
a <a>string</a> <var>input</var>, given a <dfn export for="string">position variable</dfn>
<var>position</var> tracking the position of the calling algorithm within <var>input</var>:</p>

<ol>
 <li><p>Let <var>result</var> be the empty <a>string</a>.

 <li>
  <p>While <var>position</var> doesn't point past the end of <var>input</var> and the
  <a>code point</a> at <var>position</var> within <var>input</var> meets the condition
  <var>condition</var>:

  <ol>
   <li><p>Append that <a>code point</a> to the end of <var>result</var>.

   <li><p>Advance <var>position</var> by 1.
  </ol>
 </li>

 <li><p>Return <var>result</var>.
</ol>

<p class=note>In addition to returning the collected <a>code points</a>, this algorithm updates the
<a>position variable</a> in the calling algorithm.

<p>To <dfn export>skip ASCII whitespace</dfn> within a <a>string</a> <var>input</var> given a
<a>position variable</a> <var>position</var>, <a>collect a sequence of code points</a> that are
<a>ASCII whitespace</a> from <var>input</var> given <var>position</var>. The collected
<a>code points</a> are not used, but <var>position</var> is still updated.

<hr>

<p>To <dfn export lt="strictly split|strictly split a string">strictly split a <a>string</a></dfn>
<var>input</var> on a particular delimiter <a>code point</a> <var>delimiter</var>:</p>

<ol>
 <li><p>Let <var>position</var> be a <a>position variable</a> for <var>input</var>, initially
 pointing at the start of <var>input</var>.

 <li><p>Let <var>tokens</var> be a <a>list</a> of <a>strings</a>, initially empty.

 <li><p>Let <var>token</var> be the result of <a>collecting a sequence of code points</a> that are
 not equal to <var>delimiter</var> from <var>input</var>, given <var>position</var>.

 <li><p><a for="list">Append</a> <var>token</var> to <var>tokens</var>.

 <li>
  <p>While <var>position</var> is not past the end of <var>input</var>:

  <ol>
   <li><p><a>Assert</a>: the <a>code point</a> at <var>position</var> within <var>input</var> is
   <var>delimiter</var>.

   <li><p>Advance <var>position</var> by 1.

   <li><p>Let <var>token</var> be the result of <a>collecting a sequence of code points</a> that are
   not equal to <var>delimiter</var> from <var>input</var>, given <var>position</var>.

   <li><p><a for="list">Append</a> <var>token</var> to <var>tokens</var>.
  </ol>
 </li>

 <li><p>Return <var>tokens</var>.
</ol>

<p class=note>This algorithm is a "strict" split, as opposed to the commonly-used variants
<a lt="split on ASCII whitespace">for ASCII whitespace</a> and
<a lt="split on commas">for commas</a> below, which are both more lenient in various ways involving
interspersed <a>ASCII whitespace</a>.

<p>To <dfn export lt="split on ASCII whitespace|split a string on ASCII whitespace">split a
<a>string</a> <var>input</var> on ASCII whitespace</dfn>:

<ol>
 <li><p>Let <var>position</var> be a <a>position variable</a> for <var>input</var>, initially
 pointing at the start of <var>input</var>.

 <li><p>Let <var>tokens</var> be a <a>list</a> of <a>strings</a>, initially empty.

 <li><p><a>Skip ASCII whitespace</a> within <var>input</var> given <var>position</var>.

 <li>
  <p>While <var>position</var> is not past the end of <var>input</var>:

  <ol>
   <li><p>Let <var>token</var> be the result of <a>collecting a sequence of code points</a> that are
   not <a>ASCII whitespace</a> from <var>input</var>, given <var>position</var>.

   <li><p><a for="list">Append</a> <var>token</var> to <var>tokens</var>.

   <li><p><a>Skip ASCII whitespace</a> within <var>input</var> given <var>position</var>.
  </ol>
 </li>

 <li><p>Return <var>tokens</var>.
</ol>

<p>To <dfn export lt="split on commas|split a string on commas">split a <a>string</a>
<var>input</var> on commas</dfn>:

<ol>
 <li><p>Let <var>position</var> be a <a>position variable</a> for <var>input</var>, initially
 pointing at the start of <var>input</var>.

 <li><p>Let <var>tokens</var> be a <a>list</a> of <a>strings</a>, initially empty.

 <li>
  <p>While <var>position</var> is not past the end of <var>input</var>:

  <ol>
   <li>
    <p>Let <var>token</var> be the result of <a>collecting a sequence of code points</a> that are
    not U+002C (,) from <var>input</var>, given <var>position</var>.

    <p class=note><var>token</var> might be the empty string.
   </li>

   <li><a>Strip leading and trailing ASCII whitespace</a> from <var>token</var>.

   <li><p><a for="list">Append</a> <var>token</var> to <var>tokens</var>.

   <li>
    <p>If <var>position</var> is not past the end of <var>input</var>, then:

    <ol>
     <li><p><a>Assert</a>: the <a>code point</a> at <var>position</var> within <var>input</var> is
     U+002C (,).

     <li><p>Advance <var>position</var> by 1.
    </ol>
   </li>
  </ol>
 </li>

 <li><p>Return <var>tokens</var>.
</ol>

<p>To <dfn export for=string lt=concatenate|concatenation>concatenate</dfn> a <a for=/>list</a> of
<a for=/>strings</a> <var>list</var>, using an optional separator string <var>separator</var>, run
these steps:

<ol>
 <li><p>If <var>list</var> <a for=list>is empty</a>, then return the empty string.

 <li><p>If <var>separator</var> is not given, then set <var>separator</var> to the empty string.

 <li><p>Return a <a for=/>string</a> whose contents are <var>list</var>'s <a for=list>items</a>, in
 order, separated from each other by <var>separator</var>.
</ol>

<p class=example id=example-string-concatenate>To serialize a set <var>set</var>, return the
<a for=string>concatenation</a> of <var>set</var> using U+0020 SPACE.


<h3 id=time>Time</h3>

<p>Represent time using the [=moment=] and [=duration=] specification types. Follow the advice in
[[HR-TIME-3#sec-tools]] when creating these and exchanging them with JavaScript. [[HR-TIME]]


<h2 id=data-structures>Data structures</h2>

<p>Conventionally, specifications have operated on a variety of vague specification-level data
structures, based on shared understanding of their semantics. This generally works well, but can
lead to ambiguities around edge cases, such as iteration order or what happens when you
<a for=set>append</a> an <a for=set>item</a> to an <a>ordered set</a> that the set already
<a for=set>contains</a>. It has also led to a variety of divergent notation and phrasing, especially
around more complex data structures such as <a lt="ordered map">maps</a>.

<p>This standard provides a small set of common data structures, along with notation and phrasing
for working with them, in order to create common ground.


<h3 id=lists>Lists</h3>

<p>A <dfn export>list</dfn> is a specification type consisting of a finite ordered sequence of
<dfn export for=list,stack,queue,set lt=item>items</dfn>.

<p>For notational convenience, a literal syntax can be used to express <a>lists</a>, by surrounding
the list by « » characters and separating its <a for=list>items</a> with a comma. An indexing syntax
can be used by providing a zero-based index into a list inside square brackets. The index cannot be
out-of-bounds, except when used with <a for=list>exists</a>.

<p class=example id=example-list-notation>Let |example| be the <a>list</a> « "<code>a</code>",
"<code>b</code>", "<code>c</code>", "<code>a</code>" ». Then |example|[1] is the <a>string</a>
"<code>b</code>".

<p>For notational convenience, a multiple assignment syntax may be used to assign multiple variables
to the <a>list</a>'s <a for=list>items</a>, by surrounding the variables to be assigned by « »
characters and separating each variable name with a comma. The <a>list</a>'s <a for=list>size</a>
must be the same as the number of variables to be assigned. Each variable given is then set to the
value of the <a>list</a>'s <a for=list>item</a> at the corresponding index.

<div class=example id=example-list-multiple-assignment>
 <ol>
  <li><p>Let |value| be the <a>list</a> « "<code>a</code>", "<code>b</code>", "<code>c</code>" ».

  <li><p>Let « |a|, |b|, |c| » be |value|.

  <li><p><a>Assert</a>: |a| is "<code>a</code>".

  <li><p><a>Assert</a>: |b| is "<code>b</code>".

  <li><p><a>Assert</a>: |c| is "<code>c</code>".
 </ol>
</div>

<p>When a <a>list</a>'s contents are not fully controlled, as is the case for lists from user input,
the <a>list</a>'s <a for=list>size</a> should be checked to ensure it is the expected size before
list multiple assignment syntax is used.

<div class=example id=example-list-multiple-assignment-size>
 <ol>
  <li><p>If |list|'s <a for=list>size</a> is not <code>3</code>, then return failure.
  <li><p>Let « |a|, |b|, |c| » be |list|.
 </ol>
</div>

<hr>

<p>To <dfn export for=list>append</dfn> to a <a>list</a> that is not an <a>ordered set</a> is to
add the given <a for=list>item</a> to the end of the list.

<p>To <dfn export for=list>extend</dfn> a <a>list</a> |A| with a <a>list</a> |B|,
<a for=list>for each</a> |item| of |B|, <a for=list>append</a> |item| to |A|.

<div class=example id=example-list-extend>
 <ol>
  <li><p>Let |ghostbusters| be « "<code>Erin Gilbert</code>", "<code>Abby Yates</code>" ».

  <li><p><a for=list>Extend</a> |ghostbusters| with « "<code>Jillian Holtzmann</code>",
  "<code>Patty Tolan</code>" ».

  <li><p><a>Assert</a>: |ghostbusters|'s <a for=list>size</a> is 4.

  <li><p><a>Assert</a>: |ghostbusters|[2] is "<code>Jillian Holtzmann</code>".
 </ol>
</div>

<p>To <dfn export for=list>prepend</dfn> to a <a>list</a> that is not an <a>ordered set</a> is to
add the given <a for=list>item</a> to the beginning of the list.

<p>To <dfn export for=list>replace</dfn> within a <a>list</a> that is not an <a>ordered set</a> is
to replace all items from the list that match a given condition with the given <a for=list>item</a>,
or do nothing if none do.

<p class=note>The above definitions are modified when the <a>list</a> is an <a>ordered set</a>; see
below for <a for=set lt=append>ordered set append</a>, <a for=set>prepend</a>, and
<a for=set>replace</a>.

<p>To <dfn export for=list,set>insert</dfn> an <a for=list>item</a> into a <a>list</a> before an
index is to add the given item to the list between the given index &minus; 1 and the given index. If
the given index is 0, then <a for=list>prepend</a> the given item to the list.

<p>To <dfn export for=list,set>remove</dfn> zero or more <a for=list>items</a> from a <a>list</a> is
to remove all items from the list that match a given condition, or do nothing if none do.

<div class=example id=example-list-remove>
 <p><a for=list>Removing</a> |x| from the <a>list</a> « |x|, |y|, |z|, |x| » is to remove all
 items from the list that are equal to |x|. The list now is equivalent to « |y|, |z| ».

 <p><a for=list>Removing</a> all items that start with the <a>string</a> "<code>a</code>" from the
 <a>list</a> « "<code>a</code>", "<code>b</code>", "<code>ab</code>", "<code>ba</code>" » is to
 remove the items "<code>a</code>" and "<code>ab</code>". The list is now equivalent to «
 "<code>b</code>", "<code>ba</code>" ».
</div>

<p>To <dfn export for=list,stack,queue,set>empty</dfn> a <a>list</a> is to <a for=list>remove</a>
all of its <a for=list>items</a>.

<p>A <a>list</a> <dfn export for=list,stack,queue,set lt=contain|exist>contains</dfn> an
<a for=list>item</a> if it appears in the list. We can also denote this by saying that, for a
<a>list</a> |list| and an index |index|, "|list|[|index|] <a for=list>exists</a>".

<p>A <a>list</a>'s <dfn export for=list,stack,queue,set>size</dfn> is the number of
<a for=list>items</a> the list <a for=list>contains</a>.

<p>A <a>list</a> <dfn export for=list,stack,queue,set lt="is empty|is not empty">is empty</dfn> if
its <a for=list>size</a> is zero.

<p>To <dfn export for=list,stack,queue,set lt="get the indices|indices">get the indices</dfn> of a
<a>list</a>, return <a lt="the exclusive range">the range</a> from 0 to the list's
<a for=list>size</a>, exclusive.

<p>To <dfn export for=list,set lt="iterate|for each">iterate</dfn> over a <a>list</a>, performing a
set of steps on each <a for=list>item</a> in order, use phrasing of the form
"<a for=list>For each</a> |item| of <var ignore>list</var>", and then operate on |item| in the
subsequent prose.

<p>To <dfn export for=list,stack,queue,set>clone</dfn> a <a>list</a> |list| is to create a new
<a>list</a> |clone|, of the same designation, and, <a for=list>for each</a> |item| of |list|,
<a for=list>append</a> |item| to |clone|, so that |clone| <a for=list>contains</a> the same
<a for=list>items</a>, in the same order as |list|.

<p class=note>This is a "shallow clone", as the <a for=list>items</a> themselves are not cloned in
any way.

<p class=example id=example-list-clone>Let |original| be the <a>ordered set</a> «
"<code>a</code>", "<code>b</code>", "<code>c</code>" ». <a for=set>Cloning</a> |original| creates
a new <a>ordered set</a> |clone|, so that <a for=set>replacing</a> "<code>a</code>" with
"<code>foo</code>" in |clone| gives « "<code>foo</code>", "<code>b</code>", "<code>c</code>" »,
while |original|[0] is still the <a>string</a> "<code>a</code>".

<p>To <dfn export for=list,stack,queue,set lt="sort in ascending order|sorting in ascending order|sort|sorting">sort in ascending order</dfn>
a <a>list</a> |list|, with a less than algorithm |lessThanAlgo|, is to create a new <a>list</a>
|sorted|, containing the same <a for=list>items</a> as |list| but sorted so that according to
|lessThanAlgo|, each item is less than the one following it, if any. For items that sort the same
(i.e., for which |lessThanAlgo| returns false for both comparisons), their relative order in
|sorted| must be the same as it was in |list|.

<p>To <dfn export for=list,stack,queue,set lt="sort in descending order|sorting in descending order">sort in descending order</dfn>
a <a>list</a> |list|, with a less than algorithm |lessThanAlgo|, is to create a new <a>list</a>
|sorted|, containing the same <a for=list>items</a> as |list| but sorted so that according to
|lessThanAlgo|, each item is less than the one preceding it, if any. For items that sort the same
(i.e., for which |lessThanAlgo| returns false for both comparisons), their relative order in
|sorted| must be the same as it was in |list|.

<p class=example id=example-list-sort>Let |original| be the <a>list</a> « (200, "<code>OK</code>"),
(404, "<code>Not Found</code>"), (null, "<code>OK</code>") ». <a for=list>Sorting</a> |original| in
ascending order, with |a| being less than |b| if |a|'s second <a for=struct>item</a> is
<a>code unit less than</a> |b|'s second <a for=struct>item</a>, gives the result « (404,
"<code>Not Found</code>"), (200, "<code>OK</code>"), (null, "<code>OK</code>") ».</p>

<hr>

<p>The <a>list</a> type originates from the JavaScript specification (where it is capitalized, as
<a spec=ecma-262>List</a>); we repeat some elements of its definition here for ease of reference,
and provide an expanded vocabulary for manipulating <a>lists</a>. Whenever JavaScript expects a
<a spec=ecma-262>List</a>, a <a>list</a> as defined here can be used; they are the same type.
[[!ECMA-262]]

<h4 id=stacks>Stacks</h4>

<p>Some <a>lists</a> are designated as <dfn export lt=stack>stacks</dfn>. A stack is a <a>list</a>,
but conventionally, the following operations are used to operate on it, instead of using
<a for=list>append</a>, <a for=list>prepend</a>, or <a for=list>remove</a>.

<p>To <dfn export for=stack>push</dfn> onto a <a>stack</a> is to <a for=list>append</a> to it.

<p>To <dfn export for=stack>pop</dfn> from a <a>stack</a>: if the <a>stack</a>
<a for=stack>is not empty</a>, then <a for=list>remove</a> its last <a for=stack>item</a> and return
it; otherwise, return nothing.

<p>To <dfn export for=stack>peek</dfn> into a <a>stack</a>: if the <a>stack</a>
<a for=stack>is not empty</a>, then return its last <a for=stack>item</a>; otherwise, return
nothing.

<p>Although <a>stacks</a> are <a>lists</a>, <a for=list>for each</a> must not be used with them;
instead, a combination of <a>while</a> and <a for=stack>pop</a> is more appropriate.

<h4 id=queues>Queues</h4>

<p>Some <a>lists</a> are designated as <dfn export lt=queue>queues</dfn>. A queue is a <a>list</a>,
but conventionally, the following operations are used to operate on it, instead of using
<a for=list>append</a>, <a for=list>prepend</a>, or <a for=list>remove</a>.

<p>To <dfn export for=queue>enqueue</dfn> in a <a>queue</a> is to <a for=list>append</a> to it.

<p>To <dfn export for=queue>dequeue</dfn> from a <a>queue</a> is to <a for=list>remove</a> its first
<a for=queue>item</a> and return it, if the <a>queue</a> <a for=queue>is not empty</a>, or to return
nothing if it is.

<p>Although <a>queues</a> are <a>lists</a>, <a for=list>for each</a> must not be used with them;
instead, a combination of <a>while</a> and <a for=queue>dequeue</a> is more appropriate.

<h4 id=sets>Sets</h4>

<p>Some <a>lists</a> are designated as <dfn export lt="ordered set|set">ordered sets</dfn>. An
ordered set is a <a>list</a> with the additional semantic that it must not contain the same
<a for=set>item</a> twice.

<p class=note>Almost all cases on the web platform require an <em>ordered</em> set, instead of an
unordered one, since interoperability requires that any developer-exposed enumeration of the set's
contents be consistent between browsers. In those cases where order is not important, we still use
ordered sets; implementations can optimize based on the fact that the order is not observable.

<p>To <dfn export for=set>append</dfn> to an <a>ordered set</a>: if the set <a for=list>contains</a>
the given <a for=set>item</a>, then do nothing; otherwise, perform the normal <a>list</a>
<a for=list>append</a> operation.

<p>To <dfn export for=set>prepend</dfn> to an <a>ordered set</a>: if the set
<a for=list>contains</a> the given <a for=set>item</a>, then do nothing; otherwise, perform the
normal <a>list</a> <a for=list>prepend</a> operation.

<p>To <dfn export for=set lt=replace|replacing>replace</dfn> within an <a>ordered set</a>
<var>set</var>, given <var>item</var> and <var>replacement</var>: if <var>set</var>
<a for=set>contains</a> <var>item</var> or <var>replacement</var>, then replace the first instance
of either with <var>replacement</var> and <a for=set>remove</a> all other instances.

<p class=example id=example-set-replace><a for="set">Replacing</a> "a" with "c" within the
<a>ordered set</a> « "a", "b", "c" » gives « "c", "b" ». Within « "c", "b", "a" » it gives
« "c", "b" » as well.

<p>An <a>ordered set</a> |set| is a <dfn export for=set>subset</dfn> of another <a>ordered set</a>
|superset| (and conversely, |superset| is a <dfn export for=set>superset</dfn> of |set|) if,
<a for=list>for each</a> |item| of |set|, |superset| <a for=set>contains</a> |item|.

<p class=note>This implies that an <a>ordered set</a> is both a <a for=set>subset</a> and a
<a for=set>superset</a> of itself.

<p>The <dfn export for=set>intersection</dfn> of <a>ordered sets</a> |A| and |B|, is the result
of creating a new <a>ordered set</a> |set| and, <a for=list>for each</a> |item| of |A|, if |B|
<a for=set>contains</a> |item|, <a for=set>appending</a> |item| to |set|.

<p>The <dfn export for=set>union</dfn> of <a>ordered sets</a> |A| and |B|, is the result of
<a for=list>cloning</a> |A| as |set| and, <a for=list>for each</a> |item| of |B|,
<a for=set>appending</a> |item| to |set|.

<hr>

<p><dfn export lt="the range|the inclusive range">The range</dfn> <var>n</var> to <var>m</var>,
inclusive, creates a new <a>ordered set</a> containing all of the integers from <var>n</var> up to
and including <var>m</var> in consecutively increasing order, as long as <var>m</var> is greater
than or equal to <var>n</var>.

<p><dfn export lt="the exclusive range">The range</dfn> <var>n</var> to <var>m</var>, exclusive,
creates a new <a>ordered set</a> containing all of the integers from <var>n</var> up to and including
<var>m</var> &minus; 1 in consecutively increasing order, as long as <var>m</var> is greater than
<var>n</var>. If <var>m</var> equals <var>n</var>, then it creates an empty <a>ordered set</a>.

<p class=example id=example-the-range><a for=set>For each</a> <var>n</var> of <a>the range</a> 1 to
4, inclusive, &hellip;


<h3 id=maps>Maps</h3>

<p>An <dfn export lt="ordered map|map">ordered map</dfn>, or sometimes just "map", is a
specification type consisting of a finite ordered sequence of <a for=/>tuples</a>, each consisting
of a <dfn for=map export>key</dfn> and a <dfn for=map export>value</dfn>, with no key appearing
twice. Each such tuple is called an <dfn for=map export>entry</dfn>.
<!-- TODO: we have to define key equality for this to be truly sound. -->

<p class=note>As with <a>ordered sets</a>, by default we assume that maps need to be ordered for
interoperability among implementations.

<p>A literal syntax can be used to express <a>ordered maps</a>, by surrounding the ordered map with
«[ ]» characters, denoting each of its <a for=map>entries</a> as |key| → |value|, and separating its
entries with a comma.

<p class=example id=example-map-notation>Let |example| be the <a>ordered map</a> «[
"<code>a</code>" → `<code>x</code>`, "<code>b</code>" → `<code>y</code>` ]». Then
|example|["<code>a</code>"] is the <a>byte sequence</a> `<code>x</code>`.

<hr>

<p>To <dfn export for=map lt="get|get the value">get the value of an entry</dfn> in an
<a>ordered map</a> <var>map</var> given a <a for=map>key</a> <var>key</var>:

<ol>
 <li><p>Assert: <var>map</var> <a for=map>contains</a> <var>key</var>.

 <li><p>Return the <a for=map>value</a> of the <a for=map>entry</a> in <var>map</var> whose
 <a for=map>key</a> is <var>key</var>.
</ol>

<p>We can also denote <a for=map lt=get>getting the value of an entry</a> using an indexing syntax,
by providing a <a for=map>key</a> inside square brackets directly following a <a for=/>map</a>.

<p class=example id=example-map-get>If <var ignore>map</var>["<code>test</code>"]
<a for=map>exists</a>, then return <var ignore>map</var>["<code>test</code>"].

<p>To <dfn export for=map lt="set|set the value">set the value of an entry</dfn> in an
<a>ordered map</a> to a given <a for=map>value</a> is to update the value of any existing
<a for=map>entry</a> if the map <a for=map>contains</a> an entry with the given <a for=map>key</a>,
or if none such exists, to add a new entry with the given key/value to the end of the map. We can
also denote this by saying, for an <a>ordered map</a> |map|, key |key|, and value |value|,
"<a for=map>set</a> |map|[|key|] to |value|".

<p>To <dfn export for=map lt=remove>remove an entry</dfn> from an <a>ordered map</a> is to remove
all <a for=map>entries</a> from the map that match a given condition, or do nothing if none do. If
the condition is having a certain <a for=map>key</a>, then we can also denote this by saying, for
an <a>ordered map</a> |map| and key |key|, "<a for=map>remove</a> |map|[|key|]".

<p>To <dfn export for=map>clear</dfn> an <a>ordered map</a> is to remove all <a for=map>entries</a>
from the map.

<p>An <a>ordered map</a> <dfn export for=map lt=exist|contain id=map-exists>contains an
<a for=map>entry</a> with a given key</dfn> if there exists an entry with that <a for=map>key</a>.
We can also denote this by saying that, for an <a>ordered map</a> |map| and key |key|, "|map|[|key|]
<a for=map>exists</a>".

<p>To <dfn export for=map lt="getting the keys|get the keys|keys">get the keys</dfn> of an
<a>ordered map</a>, return a new <a>ordered set</a> whose <a for=set>items</a> are each of the
<a for=map>keys</a> in the map's <a for=map>entries</a>.

<p>To <dfn export for=map lt="getting the values|get the values|values">get the values</dfn> of an
<a>ordered map</a>, return a new <a>list</a> whose <a for=list>items</a> are each of the
<a for=map>values</a> in the map's <a for=map>entries</a>.

<p>An <a>ordered map</a>'s <dfn export for=map>size</dfn> is the <a for=set>size</a> of the result
of running <a for=map>get the keys</a> on the map.

<p>An <a>ordered map</a> <dfn export for=map lt="is empty|is not empty">is empty</dfn> if its
<a for=map>size</a> is zero.

<p>To <dfn export for=map lt="iterate|for each">iterate</dfn> over an <a>ordered map</a>, performing
a set of steps on each <a for=map>entry</a> in order, use phrasing of the form
"<a for=map>For each</a> |key| → |value| of |map|", and then operate on |key| and |value| in the
subsequent prose.

<p>To <dfn export for=map>clone</dfn> an <a>ordered map</a> |map| is to create a new
<a>ordered map</a> |clone|, and, <a for=map>for each</a> |key| → |value| of |map|,
<a for=map>set</a> |clone|[|key|] to |value|.

<p class=note>This is a "shallow clone", as the <a for=map>keys</a> and <a for=map>values</a>
themselves are not cloned in any way.

<p class=example id=example-map-clone>Let |original| be the <a>ordered map</a> «[
"<code>a</code>" → «1, 2, 3», "<code>b</code>" → «» ]». <a for=set>Cloning</a> |original| creates a
new <a>ordered map</a> |clone|, so that <a for=map>setting</a> |clone|["<code>a</code>"] to
«-1, -2, -3» gives «[ "<code>a</code>" → «-1, -2, -3», "<code>b</code>" → «» ]» and leaves
|original| unchanged. However, <a for=list>appending</a> 4 to |clone|["<code>b</code>"] will modify
the corresponding <a for=map>value</a> in both |clone| and |original|, as they both point to the
same <a>list</a>.

<p>To <dfn export for=map lt="sort in ascending order|sorting in ascending order|sort|sorting">sort in ascending order</dfn>
a <a>map</a> |map|, with a less than algorithm |lessThanAlgo|, is to create a new <a>map</a>
|sorted|, containing the same <a for=map>entries</a> as |map| but sorted so that according to
|lessThanAlgo|, each entry is less than the one following it, if any. For entries that sort the same
(i.e., for which |lessThanAlgo| returns false for both comparisons), their relative order in
|sorted| must be the same as it was in |map|.

<p>To <dfn export for=map lt="sort in descending order|sorting in descending order">sort in descending order</dfn>
a <a>map</a> |map|, with a less than algorithm |lessThanAlgo|, is to create a new <a>map</a>
|sorted|, containing the same <a for=map>entries</a> as |map| but sorted so that according to
|lessThanAlgo|, each entry is less than the one preceding it, if any. For entries that sort the same
(i.e., for which |lessThanAlgo| returns false for both comparisons), their relative order in
|sorted| must be the same as it was in |map|.


<h3 id=structs>Structs</h3>

<p>A <dfn export>struct</dfn> is a specification type consisting of a finite set of
<dfn export for=struct,tuple lt=item>items</dfn>, each of which has a unique and immutable
<dfn export for=struct,tuple>name</dfn>. An <a for=struct>item</a> holds a value of a defined type.

<div class=example id=example-struct>
 <p>An <dfn ignore>email</dfn> is an example <a>struct</a> consisting of a
 <dfn ignore>local part</dfn> (a string) and a <dfn ignore>host</dfn> (a <a for=/>host</a>).

 <p>A nonsense algorithm might use this definition as follows:

 <ol>
  <li>Let <var ignore>email</var> be an email whose local part is "<code>hostmaster</code>" and host
  is <code>infra.example</code>.
  <li>&hellip;
 </ol>
</div>

<h4 id=tuples>Tuples</h4>

<p>A <dfn export>tuple</dfn> is a <a>struct</a> whose <a for=struct>items</a> are ordered. For
notational convenience, a literal syntax can be used to express <a>tuples</a>, by surrounding the
tuple with parenthesis and separating its <a for=tuple>items</a> with a comma. To use this notation,
the <a for=tuple>names</a> need to be clear from context. This can be done by preceding the first
instance with the name given to the <a>tuple</a>. An indexing syntax can be used by providing a
zero-based index into a <a>tuple</a> inside square brackets. The index cannot be out-of-bounds.

<div class=example id=example-tuple>
 <p>A <dfn ignore>status</dfn> is an example <a>tuple</a> consisting of a <dfn ignore>code</dfn> (a
 number) and <dfn ignore>text</dfn> (a byte sequence).

 <p>A nonsense algorithm that manipulates status tuples for the purpose of demonstrating their
 usage is then:</p>

 <ol>
  <li>Let |statusInstance| be the status (200, `<code>OK</code>`).
  <li>Set |statusInstance| to (301, `<code>FOO BAR</code>`).
  <li>If |statusInstance|'s code is 404, then &hellip;
 </ol>

 <p>The last step could also be written as "If |statusInstance|[0] is 404, then &hellip;". This
 might be preferable if the <a>tuple</a> <a for=tuple>names</a> do not have explicit definitions.
</div>

<p class=note>It is intentional that not all <a>structs</a> are <a>tuples</a>. Documents using the
Infra Standard might need the flexibility to add new <a for=struct>names</a> to their struct
without breaking literal syntax used by their dependencies. In that case a tuple is not appropriate.


<h2 id=json>JSON</h2>

<p class=note>The conventions used in the algorithms in this section are those of the JavaScript
specification. [[!ECMA-262]]

<p>To <dfn export lt="parse a JSON string to a JavaScript value|parsing a JSON string to a JavaScript value">parse a JSON string to a JavaScript value</dfn>,
given a <a>string</a> |string|:

<ol>
 <li><p>Return ? [$Call$](<a>%JSON.parse%</a>, undefined, « |string| »).
</ol>

<p>To <dfn export lt="parse JSON bytes to a JavaScript value|parsing JSON bytes to a JavaScript value|parse JSON from bytes">parse JSON bytes to a JavaScript value</dfn>,
given a <a>byte sequence</a> |bytes|:

<ol>
 <li><p>Let |string| be the result of running <a>UTF-8 decode</a> on |bytes|. [[!ENCODING]]

 <li><p>Return the result of <a>parsing a JSON string to a JavaScript value</a> given |string|.
</ol>

<p>To <dfn export lt="serialize a JavaScript value to a JSON string|serializing a JavaScript value to a JSON string">serialize a JavaScript value to a JSON string</dfn>,
given a JavaScript value |value|:

<ol>
 <li>
  <p>Let |result| be ? [$Call$](<a>%JSON.stringify%</a>, undefined, « |value| »).

  <p class=note>Since no additional arguments are passed to <a>%JSON.stringify%</a>, the resulting
  string will have no whitespace inserted.

 <li>
  <p>If |result| is undefined, then throw a {{TypeError}}.

  <p class="note">This can happen if |value| does not have a JSON representation, e.g., if
  it is undefined or a function.

 <li><p><a>Assert</a>: |result| is a <a>string</a>.

 <li><p>Return |result|.
</ol>

<p>To <dfn export lt="serialize a JavaScript value to JSON bytes|serializing a JavaScript value to JSON bytes|serialize JSON to bytes">serialize a JavaScript value to JSON bytes</dfn>,
given a JavaScript value |value|:

<ol>
 <li><p>Let |string| be the result of <a>serializing a JavaScript value to a JSON string</a> given
 |value|.

 <li><p>Return the result of running <a>UTF-8 encode</a> on |string|. [[!ENCODING]]
</ol>

<hr>

<p>The above operations operate on JavaScript values directly; in particular, this means that
the involved objects or arrays are tied to a particular <a lt="realm">JavaScript realm</a>. In
standards, it is often more convenient to convert between JSON and realm-independent <a>maps</a>,
<a>lists</a>, <a>strings</a>, <a>booleans</a>, numbers, and nulls.

<p>To <dfn export lt="parse a JSON string to an Infra value|parsing a JSON string to an Infra value|parse JSON into Infra values">parse a JSON string to an Infra value</dfn>,
given a <a>string</a> |string|:

<ol>
 <li><p>Let |jsValue| be ? [$Call$](<a>%JSON.parse%</a>, undefined, « |string| »).

 <li><p>Return the result of [=converting a JSON-derived JavaScript value to an Infra value=], given
 |jsValue|.
</ol>

<p>To <dfn export lt="parse JSON bytes to an Infra value|parsing JSON bytes to an Infra value">parse JSON bytes to an Infra value</dfn>,
given a <a>byte sequence</a> |bytes|:

<ol>
 <li><p>Let |string| be the result of running <a>UTF-8 decode</a> on |bytes|. [[!ENCODING]]

 <li><p>Return the result of <a>parsing a JSON string to an Infra value</a> given |string|.
</ol>

<p>To <dfn lt="convert a JSON-derived JavaScript value to an Infra value|converting a JSON-derived JavaScript value to an Infra value">convert a JSON-derived JavaScript value to an Infra value</dfn>,
given a JavaScript value |jsValue|:

<ol>
 <li><p>If [$Type$](|jsValue|) is Null, Boolean, String, or Number, then return |jsValue|.

 <li>
  <p>If [$IsArray$](|jsValue|) is true, then:

   <ol>
    <li><p>Let |result| be an empty [=list=].

    <li><p>Let |length| be ! [$ToLength$](! [$Get$](|jsValue|, "<code>length</code>")).

    <li>
      <p>[=list/For each=] |index| of [=the range=] 0 to |length| &minus; 1, inclusive:

      <ol>
       <li><p>Let |indexName| be ! [$ToString$](|index|).

       <li><p>Let |jsValueAtIndex| be ! [$Get$](|jsValue|, |indexName|).

       <li><p>Let |infraValueAtIndex| be the result of [=converting a JSON-derived JavaScript value to an Infra value=],
       given |jsValueAtIndex|.

       <li><p>[=list/Append=] |infraValueAtIndex| to |result|.
      </ol>
    </li>

    <li><p>Return |result|.
   </ol>
 </li>

 <li><p>Let |result| be an empty [=ordered map=].

 <li>
  <p>[=list/For each=] |key| of ! |jsValue|.\[[OwnPropertyKeys]]():

   <ol>
    <li><p>Let |jsValueAtKey| be ! [$Get$](|jsValue|, |key|).

    <li><p>Let |infraValueAtKey| be the result of [=converting a JSON-derived JavaScript value to an Infra value=],
    given |jsValueAtKey|.

    <li><p>[=map/Set=] |result|[|key|] to |infraValueAtKey|.
   </ol>
 </li>

 <li><p>Return |result|.
</ol>

<p>To <dfn export lt="serialize an Infra value to a JSON string|serializing an Infra value to a JSON string">serialize an Infra value to a JSON string</dfn>,
given a <a>string</a>, <a>boolean</a>, number, null, <a>list</a>, or <a>string</a>-keyed <a>map</a>
|value|:

<ol>
 <li><p>Let |jsValue| be the result of
 <a>converting an Infra value to a JSON-compatible JavaScript value</a>, given |value|.

 <li>
  <p>Return ! [$Call$](<a>%JSON.stringify%</a>, undefined, « |jsValue| »).

  <p class=note>Since no additional arguments are passed to <a>%JSON.stringify%</a>, the resulting
  string will have no whitespace inserted.
</ol>

<p>To <dfn export lt="serialize an Infra value to JSON bytes|serializing an Infra value to JSON bytes">serialize an Infra value to JSON bytes</dfn>,
given a <a>string</a>, <a>boolean</a>, number, null, <a>list</a>, or <a>string</a>-keyed <a>map</a>
|value|:

<ol>
 <li><p>Let |string| be the result of <a>serializing an Infra value to a JSON string</a>, given
 |value|.

 <li><p>Return the result of running <a>UTF-8 encode</a> on |string|. [[!ENCODING]]
</ol>

<p>To <dfn lt="convert an Infra value to a JSON-compatible JavaScript value|converting an Infra value to a JSON-compatible JavaScript value">convert an Infra value to a JSON-compatible JavaScript value</dfn>,
given |value|:

<ol>
 <li><p>If |value| is a <a>string</a>, <a>boolean</a>, number, or null, then return |value|.

 <li>
  <p>If |value| is a <a>list</a>, then:

  <ol>
   <li><p>Let |jsValue| be ! [$ArrayCreate$](0).

   <li><p>Let |i| be 0.

   <li>
    <p><a for=list>For each</a> |listItem| of |value|:

    <ol>
     <li><p>Let |listItemJSValue| be the result of
     <a>converting an Infra value to a JSON-compatible JavaScript value</a>, given |listItem|.

     <li><p>Perform ! [$CreateDataPropertyOrThrow$](|jsValue|, ! [$ToString$](|i|),
     |listItemJSValue|).

     <li><p>Set |i| to |i| + 1.
    </ol>

   <li><p>Return |jsValue|.
  </ol>

 <li><p>Assert: |value| is a <a>map</a>.

 <li><p>Let |jsValue| be ! [$OrdinaryObjectCreate$](null).

  <li>
   <p><a for=list>For each</a> |mapKey| → |mapValue| of |value|:

   <ol>
    <li><p>Assert: |mapKey| is a <a>string</a>.

    <li><p>Let |mapValueJSValue| be the result of
    <a>converting an Infra value to a JSON-compatible JavaScript value</a>, given |mapValue|.

    <li><p>Perform ! [$CreateDataPropertyOrThrow$](|jsValue|, |mapKey|, |mapValueJSValue|).
   </ol>

  <li><p>Return |jsValue|.
 </ol>
</ol>


<h2 id=forgiving-base64>Forgiving base64</h2>

<p>To <dfn export>forgiving-base64 encode</dfn> given a <a>byte sequence</a> <var>data</var>, apply
the base64 algorithm defined in section 4 of RFC 4648 to <var>data</var> and return the result.
[[!RFC4648]]

<p class="note no-backref">This is named <a>forgiving-base64 encode</a> for symmetry with
<a>forgiving-base64 decode</a>, which is different from the RFC as it defines error handling for
certain inputs.

<p>To <dfn export>forgiving-base64 decode</dfn> given a string <var>data</var>, run these steps:</p>

<ol>
 <li><p>Remove all <a>ASCII whitespace</a> from <var>data</var>.
 <!-- https://lists.w3.org/Archives/Public/public-whatwg-archive/2011May/0207.html -->

 <li>
  <p>If <var>data</var>'s <a for=string>code point length</a> divides by 4 leaving no remainder,
  then:

  <ol>
   <li><p>If <var>data</var> ends with one or two U+003D (=) <a>code points</a>, then remove them
   from <var>data</var>.
  </ol>

 <li><p>If <var>data</var>'s <a for=string>code point length</a> divides by 4 leaving a remainder of
 1, then return failure.

 <li>
  <p>If <var>data</var> contains a <a>code point</a> that is not one of

  <ul class="brief">
   <li>U+002B (+)
   <li>U+002F (/)
   <li><a>ASCII alphanumeric</a>
  </ul>

  <p>then return failure.

 <li><p>Let <var>output</var> be an empty <a>byte sequence</a>.

 <li><p>Let <var>buffer</var> be an empty buffer that can have bits appended to it.

 <li><p>Let <var>position</var> be a <a>position variable</a> for <var>data</var>, initially
 pointing at the start of <var>data</var>.

 <li>
  <p>While <var>position</var> does not point past the end of <var>data</var>:

  <ol>
   <li><p>Find the <a>code point</a> pointed to by <var>position</var> in the second column of
   Table 1: The Base 64 Alphabet of RFC 4648. Let <var>n</var> be the number given in the first cell
   of the same row. [[!RFC4648]]

   <li><p>Append the six bits corresponding to <var>n</var>, most significant bit first, to
   <var>buffer</var>.

   <li><p>If <var>buffer</var> has accumulated 24 bits, interpret them as three 8-bit big-endian
   numbers. Append three bytes with values equal to those numbers to <var>output</var>, in the same
   order, and then empty <var>buffer</var>.

   <li><p>Advance <var>position</var> by 1.
  </ol>

 <li>
  <p>If <var>buffer</var> is not empty, it contains either 12 or 18 bits. If it contains 12 bits,
  then discard the last four and interpret the remaining eight as an 8-bit big-endian number. If it
  contains 18 bits, then discard the last two and interpret the remaining 16 as two 8-bit big-endian
  numbers. Append the one or two bytes with values equal to those one or two numbers to
  <var>output</var>, in the same order.</p>

  <p class="note">The discarded bits mean that, for instance, "<code>YQ</code>" and
  "<code>YR</code>" both return `<code>a</code>`.

 <li><p>Return <var>output</var>.
</ol>


<h2 id=namespaces>Namespaces</h2>

<p>The <dfn export>HTML namespace</dfn> is "<code>http://www.w3.org/1999/xhtml</code>".

<p>The <dfn export>MathML namespace</dfn> is "<code>http://www.w3.org/1998/Math/MathML</code>".

<p>The <dfn export>SVG namespace</dfn> is "<code>http://www.w3.org/2000/svg</code>".

<p>The <dfn export>XLink namespace</dfn> is "<code>http://www.w3.org/1999/xlink</code>".

<p>The <dfn export>XML namespace</dfn> is "<code>http://www.w3.org/XML/1998/namespace</code>".

<p>The <dfn export>XMLNS namespace</dfn> is "<code>http://www.w3.org/2000/xmlns/</code>".


<h2 class=no-num id=acknowledgments>Acknowledgments</h2>

<p>Many thanks to
Addison Phillips,
Andreu Botella,
Aryeh Gregor,
Ben Kelly,
Chris Rebert,
Daniel Ehrenberg,
Dominic Farolino,
Gabriel Pivovarov,
Ian Hickson,
Jakob Ackermann<!-- das7pad; GitHub -->,
Jake Archibald,
Jeff Hodges,
Jeffrey Yasskin,
Jungkee Song,
Leonid Vasilyev,
Maciej Stachowiak,
Malika Aubakirova,
Martin Thomson,
Michael™ Smith,
Mike West,
Mike Taylor,
Ms2ger,
Pavel "Al Arz" Kurochkin,
Philip Jägenstedt,
Rashaun "Snuggs" Stovall,
Sergey Shekyan,
Simon Pieters,
Tab Atkins,
Tobie Langel,
triple-underscore,
Wolf Lammen,
and Xue Fuqiao
for being awesome!

<p>This standard is written by <a lang=nl href=https://annevankesteren.nl/>Anne van Kesteren</a>
(<a href=https://www.apple.com/>Apple</a>, <a href=mailto:annevk@annevk.nl>annevk@annevk.nl</a>) and
<a href=https://domenic.me/>Domenic Denicola</a> (<a href=https://www.google.com/>Google</a>,
<a href=mailto:d@domenic.me>d@domenic.me</a>).