Pseudocode for parsing Link headers

link_pseudo.md

Parsing a Header Set for Links

This algorithm can be used to parse the Link header fields that a HTTP header set contains. Given a header_set of (string field_name, string field_value) pairs, assuming ASCII encoding, it returns a list of link objects.

1. Let field_values be a list containing the members of header_set whose field_name is a case-insensitive match for "link".

2. Let links be an empty list.

3. For each field_value in field_values:

   1. Let value_links be the result of Parsing A Link Field Value from field_value.

   2. Append each member of value_links to links.

4. Return links.

Parsing a Link Field Value

This algorithm parses zero or more comma-separated link-values from a Link header field. Given a string field_value, assuming ASCII encoding, it returns a list of link objects.

1. Let links be an empty list.

2. While field_value has content:

   1. Consume any leading OWS.

   2. If the first character is not "<", return links.

   3. Discard the first character ("<").

   4. Consume up to but not including the first ">" character or end of field_value and let the result be target_string.

   5. If the next character is not ">", return links.

   6. Discard the leading ">" character.

   7. Let link_parameters, be the result of Parsing Parameters from field_value (consuming zero or more characters of it).

   8. Let target be the result of relatively resolving (as per {{RFC3986}}, Section 5.2) target_string. Note that any base URI carried in the payload body is NOT used.

   9. Let relations_string be the second item of the first tuple of link_parameters whose first item matches the string "rel", or the empty string ("") if it is not present.

   10. Split relations_string on RWS (removing it in the process) into a list of strings relation_types.

   11. Let context_string be the second item of the first tuple of link_parameters whose first item matches the string "anchor". If it is not present, context_string is the identity of the representation carrying the Link header {{RFC7231}}, Section 3.1.4.1, serialised as a URI. Where the identity is "anonymous" context_string is null.

   12. Let context be the result of relatively resolving (as per {{RFC3986}}, Section 5.2) context_string, unless context_string is null in which case context is null. Note that any base URI carried in the payload body is NOT used.

   13. Let target_attributes be an empty list.

   14. For each tuple (param_name, param_value) of link_parameters:

       1. If param_name matches "rel" or "anchor", skip this tuple.

       2. If param_name matches "media", "title", "title*" or "type" and target_attributes already contains a tuple whose first element matches the value of param_name, skip this tuple.

       3. Append (param_name, param_value) to target_attributes.

   15. Let star_param_names be the set of param_names in the (param_name, param_value) tuples of link_parameters where the last character of param_name is an asterisk ("*").

   16. For each star_param_name in star_param_names:

       1. Let base_param_name be star_param_name with the last character removed.

       2. If the implementation does not choose to support an internationalised form of a parameter named base_param_name for any reason (including, but not limited to, it being prohibited by the parameter's specification), remove all tuples from link_parameters whose first member is star_param_name and skip to the next star_param_name.

       3. Remove all tuples from link_parameters whose first member is base_param_name.

       4. Change the first member of all tuples in link_parameters whose first member is star_param_name to base_param_name.

   17. For each relation_type in relation_types:

       1. Case-normalise relation_type to lowercase.

       2. Append a link object to links with the target target, relation type of relation_type, context of context, and target attributes target_attributes.

3. Return links.

Parsing Parameters

This algorithm parses the parameters from a header field value. Given an ASCII string input, it returns a list of (string parameter_name, string parameter_value) tuples that it contains. input is modified to remove the parsed parameters.

1. Let parameters be an empty list.

2. While input has content:

   1. Consume any leading OWS.

   2. If the first character is not ";", return parameters.

   3. Discard the leading ";" character.

   4. Consume any leading OWS.

   5. Consume up to but not including the first BWS, "=", ";", "," character or end of input and let the result be parameter_name.

   6. Consume any leading BWS.

   7. If the next character is "=":

      1. Discard the leading "=" character.

      2. Consume any leading BWS.

      3. If the next character is DQUOTE, let parameter_value be the result of Parsing a Quoted String from input (consuming zero or more characters of it).

      4. Else, consume the contents up to but not including the first ";", "," character or end of input and let the results be parameter_value.

      5. If the last character of parameter_name is an asterisk ("*"), decode parameter_value according to {{I-D.ietf-httpbis-rfc5987bis}}. Continue processing input if an unrecoverable error is encountered.

   8. Else:

      1. Let parameter_value be an empty string.

   9. Case-normalise parameter_name to lowercase.

   10. Append (parameter_name, parameter_value) to parameters.

   11. Consume any leading OWS.

   12. If the next character is "," or the end of input, stop processing input and return parameters.

Parsing a Quoted String

This algorithm parses a quoted string, as per {{RFC7230}}, Section 3.2.6. Given an ASCII string input, it returns an unquoted string. input is modified to remove the parsed string.

1. Let output be an empty string.

2. If the first character of input is not DQUOTE, return output.

3. Discard the first character.

4. While input has content:

   1. If the first character is a backslash ("\"):

      1. Discard the first character.

      2. If there is no more input, return output.

      3. Else, consume the first character and append it to output.

   2. Else, if the first character is DQUOTE, discard it and return output.

5. Return output.

I think this goes into the right direction; it's mostly a parser based on a relaxed ABNF transformed to prose (which makes me wonder whether there's a tool to be written here :-).

Other comments:

1. "... If it is not present, context_string is the identity of the representation carrying the Link header ..." - similar prose is elsewhere in the spec - what is "the identity of a representation"?????
2. "Consume the contents up to but not including the first DQUOTE character that is not preceded by a "" character" - I assume there's a backslash missing here. That said: doesn't work, because it would fail for an input such as: "\\" - here, the DQUOTE is preceded by backslash, but it's not part of the quoted-pair.

@reschke -

1. Did you read the linked text? Would it be better if s/identity/URL/?

2. Will fix.

OK, have another look.