A REST API must not define fixed resource names or hierarchies (an obvious coupling of client and server). Servers must have the freedom to control their own namespace. Instead, allow servers to instruct clients on how to construct appropriate URIs, such as is done in HTML forms and URI templates, by defining those instructions within media types and link relations.
Fielding - 2008 (Emphasis added).
The litmus test being, can the server publish a new URI template without breaking clients?
Working through the WWW analog...
How do we language an HTML form POST in the rest style? The form inputs are sent to the web server with a specific media type (by default:
application/x-www-form-urlencoded ). So what are the input parameters? They are descriptions of additional constraints on the data that the server is expecting. In other words, they are analogous to a custom media type (application/prs.esben.user-search-form+urlencoded, perhaps).
So your hypermedia describes a search as a POST of your custom media type to some resource. What's the RESTful way for the server to handle this request?
A trivial implementation would be to use the encoded data to identify a new resource that represents the result set of the query, and redirect the user agent to that new resource. So POST /searches (color=blue) redirects to /searches?color=blue, and then the user agent follows that redirect to GET the results. This retrieval of the resources is safe, and can be fetched from a cache rather than dispatching the message all the way to the server. So everything is good in this implementation.
What does that implementation look like? It's just a transform of the representation of the search (in the customized media type) to a resource identifier.
What changes when we use GET, rather than POST, as the form method? Really, we're just transferring the execution of that code from the server to the browser.
How does that work? The application state is being delivered to the browser using the media-type text/html. Just as the shared understanding of this media type tells the browser that
<form method="post" ...>
means "this is a link with a customized media type, described by the following constraints", so to does
<form method="get" ...>
tells the browser that "this is a link that relies upon customized uri construction, described by the following constraints"
So that's the answer for RMM-3; the description of your media type includes a specification for how constructed identifiers are described in the hypermedia (ie: the template, but also how (if) the the template parameters are constrained).
For an example of this, take a look at the specification of HAL.