Converting the URI query to JSON
This post will provide more generic (canonical) approach toward the problem of extraction of the variables from the URI string.
The query is defined across several descriptive standards (RFCs and specifications), so tho have canonical approach, we need to use the specifications to create a normalized form of the query before we can build the object.
TL;DR
To assure that we can be implement the specifications with the ability to cater for future extensions, the algorithm to convert the query to JSON should be separated in steps, each one gradually building the normalized form of the query, before it can be converted to JSON object. To do so, we need the following steps:
- Extract the query from the URI
- Split to
key=value
- Normalize the
key (build the object hierarchy)
- Normalize the
value (populate the object attributes and build the attribute arrays)
- Build JSON object based on the normalized
key=value
Such separation of the steps will allow much easier adoption of future changes in the specifications. The parsing of the values can be done with RegEx or with a parser (BNF, PEG, etc.).
Conversion steps
First thing to be done is to extract the query string from the URI. This is described in the RFC3986 and will be explained in it's own section Extracting the query string. The extraction of the query segment, as we will see later, can be easily done with RegEx.
After query string is extracted from the URI, one needs to interpret the information conveyed by the query. As we will see below, the query has a very loose definition in the RFC3986, and the case where the query is conveying variables is further elaborated in RFC6570. During the extraction, the algorithm should extract the values (that are in form of key=value) and store them in a map structure (one approach would be to use strict as described in following SO post. The section Interpreting the query string provides overview of the process.
After the variables are separated and placed in form of key=value, next stage is to normalize the key. Proper interpretation of the key will allow us to build the hierarchical structure of the JSON object from the key=value structure. The RFC6570 is not providing much information on how the key can be normalized, however the OpenAPI specification provides a good information how to handle different types of key. The normalization will be further elaborated in section Normalizing the key
Next we need to normalize the variables by continuing to build on the RFC6570 which defines the types of the variables in several levels. This will be further elaborated in section Normalizing the value
Final stage is to build the JSON object with cJSON_AddItemToObject(query, name, cJSON_CreateString(value));. More details will be discussed in the Building the JSON Object section.
During implementation, some of the steps can be merged to a single step to optimize the implementation.
Extracting the query string
The RFC3986 which is the main descriptive standard that is governing the URI is defining the URI as:
URI = scheme ":" hier-part [ "?" query ] [ "#" fragment ]
The query part is defined in the section 3.4 of the RFC as the segment of the URI such as:
... The query component is indicated by the first question
mark ("?") character and terminated by a number sign ("#") character
or by the end of the URI. ...
The formal syntax of the query segment is defined as:
query = *( pchar / "/" / "?" )
pchar = unreserved / pct-encoded / sub-delims / ":" / "@"
unreserved = ALPHA / DIGIT / "-" / "." / "_" / "~"
pct-encoded = "%" HEXDIG HEXDIG
sub-delims = "!" / "$" / "&" / "'" / "(" / ")"
/ "*" / "+" / "," / ";" / "="
This means that the query can contain more instances of ? and / before the # is met. Actually, as long as the characters after first occurrence of the? are in the set of characters that do not have special meaning, everything that is found until first # is encountered is the query.
At the same time, this also implies that the sub-delimiter &, as well as the ? has no special meaning according to this RFC when is encountered inside the query string, as long as it's in the proper form and position in the URI. This implies that each implementation can define its own structure. The language of RFC in chapter 3.4 confirms such implications by leaving space for other interpretations by using often instead of always
... However, as query components
are often used to carry identifying information in the form of
"key=value" pairs ...
In addition, the RFC also provides the following RegEx that can be used to extract the query part from the URI:
regex : ^(([^:/?#]+):)?(//([^/?#]*))?([^?#]*)(\?([^#]*))?(#(.*))?
segments: 12 3 4 5 6 7 8 9
Where the capture #7 is the query from the URI.
The easiest approach for extracting the query, provided that we are not interested in the remaining parts of the URI, is to use the RegEx to split the URI and extract the query string that will not contain the leading ? nor the terminating #.
This RFC3986 is further extended with the RFC3987 in order to cover the international characters, however the RegEx defined by the RFC3986 remains valid
Extracting variables from the query string
To decompose the query string to key=value pairs, we need to do reverse engineering of the RFC6570 which establishes a descriptive standard for the expansion of the variables and constructing the valid query. As the RFC is stating
... A URI Template provides both a structural description of a URI space
and, when variable values are provided, machine-readable instructions
on how to construct a URI corresponding to those values. ...
From the RFC, we can extract the following syntax for a variable in the query:
query = variable *( "&" variable )
variable = varname "=" varvalue
varvalue = *( valchar / "[" / "] / "{" / "}" / "?" )
varname = varchar *( ["."] varchar )
varchar = ALPHA / DIGIT / "_" / pct-encoded
pct-encoded = "%" HEXDIG HEXDIG
valchar = unreserved / pct-encoded / vsub-delims / ":" / "@"
unreserved = ALPHA / DIGIT / "-" / "." / "_" / "~"
vsub-delims = "!" / "$" / "'" / "(" / ")"
/ "*" / "+" / ","
The extraction can be performed with a parser that implements the above grammar, or by iterating over the query with the following RegEx and extracting the (key, value) pairs.
([\&](([^\&]*)\=([^\&]*)))
In case we use RegEx, note that in previous section we had omitted the "?" at the start of the query and "#" at the end, so we need don't need to handle this characters in the separation of the variables.
Normalizing the key
There descriptive standard RFC6570 provides generic rules of the format of the key, the RFC is not helping much when it comes to the rules for the interpretation of the key when an object is constructed. Some of the specifications such as the OpenAPI specification, JSON API Specification), etc. can help with the interpretation, but they are not providing the full set of rules, rather a subset. To make the things wort, some of the SDKs (ex. PHP SDK) have its own rules for building the keys.
In such situation, the best approach is to create a hierarchical rules for key normalization that will convert the key to a unified format, similar to json path dot notation. The hierarchical rules will allow us to control how the ambiguous situations (in case of collisions between specifications), but controlling the order of the rules. The json path notation will allow us to build the object in the final step without the necessity to have proper order of the key=value pairs.
Following is the grammar of the normalized format:
key = sub-key *("." sub-key )
sub-key = name [ ("[" index "]") ]
name = *( varchar )
index = NONZERO-DIGIT *( DIGIT )
This grammar will allow for keys such as foo, foo.baz, foo[0].baz, foo.baz[0], foo.bar.baz etc.
Following are a good starting point to set of rules and the transformation
- Flat key (
key -> key)
- Attribute key (
key.atr -> key.atr)
- Array key (
key[] -> key[0])
- Object Array key (
key[attribute] -> key.attribute), (key[][attribute] -> key[0].attribute), (key[attribute][] -> key.attribute[0])
More rules can be added to address special cases. During the transformation, the algorithm should pass from the most specific rules (the bottom rules) to the most generic rules and try to find a full match. If a full match if found, the key will be overwritten with the normal form and the remaining rules will be skipped.
Normalizing the value
Similar to the normalization of the key, the value should also be normalized in cases where the value represents a list. We will need to convert the value from the arbitrary list format to the form format (coma separated list) which is defined by the following grammar:
value = singe-value *( "," singe-value )
singe-value = *( unreserved / pct-encoded )
This grammar will allow us the value to take form a, a,b, a,b,c, etc.
Extracting the list of the values from the value string can be done with splitting the string by the valid delimiters (",",";","|", etc.) and producing the list in a normalized form.
Building the JSON Object
Once the keys and the values are normalized, converting the flat list (the map structure) to a JSON Object can be done by a singe pass trough all of the keys in the list. The normalized format of the key will help us, since the key conveys the whole information about his hierarchy in the object, so even if we had not encountered some of the intermediate attributes, we are able to build the object.
Similar, we can recognize if the value of the attribute should be a flat string or an array from the variable itself, so here as well, no additional information is required to create the proper representation.
Alternative approach
As alternative approach, we can construct a full grammar that will create the AST (abstract syntax tree), and use the tree to produce the JSON object, however due to the multiple variations of the formats and ability to have future extensions, this approach will be less flexible.
Useful links
