URI Parameter ambiguity


#1

The URI template spec only covers applying parameters to the template.

For example:

foo/{x}abc

If x = abcabc, the result when applied to the template is

foo/abcabcabc

The spec does not cover how the URI parameter matching should occur, is it left to right? right to left?

if it is left to right, then

/foo/abcabcabc does not match foo/{x}abc

If it right to left, then it does, and the parameter x = abcabc and we get the same result when we substitute, produce a URI, and then match again.

Unless I’m missing something, I think the matching should be right to left (greedy) to make the above work. However, I am unsure if that breaks some other case.

However:
/foo/{x}abc{y} where x = abc and y = abc yields /foo/abcabcabc. Matching the pattern to that, if x is greedily assigned abcabc before evaluating y, then y won’t match.

I am losing faith that URI templates were the right choice. They are a useful tool for applying parameters, but seem woefully ambiguous and unsound for matching in non-trivial cases. The two parameter case above has multiple possible matches for x and y independently, and one solution that satisfies both. But one can easily construct a case where there are N possible solutions. Here is one with 2:

/foo/{x}Z{y} , x=ZZ; y=Z substitute => /foo/ZZZZ match => ??? two solutions: x=Z, y=ZZ OR x=ZZ, y=Z

There is probably some way to specify which choice should be taken when matching but the many of these are not simple to implement – the full solution space is exponential in size where exponent is the number of parameters. For example, in the above, the possible solutions are nx * ny where nx is the number of possible matches for x, and ny is the number of solutions for y. If the number of parameters double, the solution space expands exponentially.
I think something designed with the intention of both substitution and matching as inverses (e.g. not the URI template spec) would have been a better idea - but that problem may be fundamentally hard.

Alternatively, if parameters were automatically forbidden to be the same value as a neighbor fragment it would work. For example, in the /foo/{x}abc{y} case, x and y can not contain abc. If if y=qabcq it becomes ambiguous…

Any suggestions for how to move forward on a server side matching implementation for 1.0 are welcome. At this point I’m going to significantly limit what is allowed from what the spec contains.

  • No ‘/’ characters, these must be URL encoded. URI templates level 1, basically.
  • Always match one-or-more, not zero-or-more characters, no optional parameters
  • Greedy right-to-left matching for the right-most parameter
  • Minimal, left-to-right matching for all other parameters, at least one character match.

Three parameter sequences will still be problematic, but it works for the above examples.

/foo/A{x}A{y}A{z}A ; x = y = z = AA; => /foo/AAAAAAAAAA

  • left to right literal match: /foo/A, remainder literal AAAAAAAAA remainder match {x}A{y}A{z}A
  • minimal left-to-right match for x means x=A. remaining literal AAAAAAA
  • minimal left-to-right match for y means y=A. remaining literal AAAAA
  • greedy match for z. z=AAAA,

Note, I see 10 possible solutions at first glance, this picks the one where the third parameter is max length

This is easier to implement because the first solution encountered is taken at each step. The right-most parameter having special rules is somewhat sane, as there are other cases where it has to anyway since it may not be bounded on the right side and could support having / in it or matching an empty string without the same problems that happen to the other parameters.


#2

Another thing I don’t see in the spec. This should be invalid, even if it is a valid template URI it is ambiguous:

/foo/{x}{y} paramters have to have at least one character between them for it to make sense in a match. Does /foo/bar match? If so, what is x and what is y?

The algorithm I have above would minimally assign b to x, then the remainder ar eagerly to y. That is a good sign, but I have not formally proven that it works in general.