Matching algorithm for resources

From: Paul Sandoz <Paul.Sandoz_at_Sun.COM>
Date: Tue, 24 Apr 2007 10:44:46 +0200

Hi

Given the blink sale example (see below for Java classes presented in
another email) i thought it would be useful to describe how the matching
algorithm works (which Marc and I have implemented and experimented with).

See attached for a description that i hope helps explain things in more
detail.

Paul.

@UriTemplate("/invoices")
@SubResources({InvoiceResource.class})
class InvoicesResource {

     Date start, end;
     String status, tags;

     public InvoicesResource(
          @QueryParam("start") Date start,
          @QueryParam("end") Date end,
          @QueryParam("status") String status,
          @QueryParam("tags") String tags)
        ...
     }

     @ProduceMime("application/vnd.blinksale+xml")
     @HttpMethod
     Invoices getInvoices() {
        ...
     }

     @ProduceMime("application/atom+xml")
     @HttpMethod
     Feed getInvoicesAsFeed() {
        ...
     }

     @ProduceMime("text/calendar")
     @HttpMethod
     Calendar getInvoicesAsCalendar() {
        ...
     }

     @ConsumeMime("application/vnd.blinksale+xml'")
     @HttpMethod
     Created postInvoice(Invoice i) {
        ...
     }

}

@UriTemplate("{invoice_Id}")
class InvoiceResource {

     int id;

     public InvoiceResource(
          @UriParam("invoice_Id}" int id) {
        if (id not recognized)
          throw NotFoundException(...);

        this.id = id;
     }

     @ProduceMime("application/vnd.blinksale+xml'")
     @HttpMethod
     Invoice getInvoice() {
        ...
     }

     @ProduceMime("application/atom+xml")
     @HttpMethod
     Entry getInvoicesAsEntry() {
        ...
     }

     @ConsumeMime("application/vnd.blinksale+xml'")
     @HttpMethod
     void putInvoice(Invoice i) {
        ...
     }

     @HttpMethod
     void deleteInvoice() {
        ...
     }

     @UriTemplate("deliveries")
     DeliveriesResource getDeliveriesResource () {
         return new DeliveriesResource(i);
     }

     @UriTemplate("payments")
     PaymentsResource getPaymentsResource () {
         return new PaymentsResource(i);
     }
}

-- 
| ? + ? = To question
----------------\
    Paul Sandoz
         x38109
+33-4-76188109

Static resource: a resource whose corresponding concrete Java class is known statically to the runtime. Such resources are:

Java classes annotated with @UriTemplate that has an absolute URI template (begins with a '/');
Java classes referenced by a @SubResources declared on a Java class that is a resource.

Dynamic resource: a resource whose corresponding to a concrete Java class cannot be determined statically and is determined dynamically by the application. Such a resource is the concrete Java class of a Java object returned from a Java method annotated with a @UriTemplate.

The resource matching algorithm is a recursive algorithm that consumes the URI path, from left to right, in accordance to the matching URI templates of resources and the sub-relationship between resources corresponding to the hierarchy of the URI path.

The algorithm can be specified using regular expressions since a URI template can be converted to a regular expression.

NOTE – The algorithm can be easily implemented using regular expressions but can also be implemented using more optimal mechanisms as long as the results are the same. Furthermore regular expressions may be coalesced for statically determined sub-relationships as long as the results are the same.

For a resource containing sub-resources the regular expression generated from the URI template associated with that resource is augmented with the expression “(/.*)?” that represents the matching group for the right-hand-side of the URI path that will be matched against sub-resources. This matching group will always be the last matching group, matching groups for template values will always occur before. For a resource containing no sub-resources the regular expression is augmented with “(/)?”.

NOTE – Using “(/.*)?” or “(/)?” enables the runtime to perform automatic redirection for cases where a URI template ends with a slash but the URI path does not. For example if a resource has the URI template “/invoices/” and the URI path is “/invoices” then the runtime can detect this and automatically send an HTTP redirect to “/invoices/”.

A resource having one or more sub-resources will have one or more URI templates and therefore one or more regular expressions to match against. The regular expressions are ordered as follows:

The regular expression with the most matching groups is ordered first; and
If two regular expressions have the same number of matching groups then the most explicit expression is ordered first.

The URI path is matched against each regular expressions (in order) until a matching expression is found. If no matching expression is found then a resource cannot be found for the URI path. If a matching expression is found then the matching right-hand path (the last matching group) is obtained and this becomes the new URI path to match against a new set of URI templates obtained from the matching sub-resource.

The algorithm terminates when the URI path is consumed. A Java method that is capable of processing the HTTP request will then be invoked on the last matched resource obtained by the algorithm.

The following table presents an example using the BlinkSale API for the URI path “/invoices/1/deliveries/2” where each segment of the path corresponds to a resource and a Java class corresponding to a resource references its sub-resources using static or dynamic mechanisms.

Step	URI path	URI templates	Matching regular expression	Matching groups
1	/invoices/1/deliveries/2	/clients /invoices	/invoices(/.*)?	(/1/deliveries/2)
2	/1/deliveries/2	{invoice_id}	/(.?)(/.)?	(1, /deliveries/2)
3	/deliveries/2	/deliveries /payments	/deliveries(/.*)?	(/2)
4	/2	{delivery_id}	/(.?)(/.)?	(2, null)
5	null

At step 5 the Java method that is capable of processing the HTTP request will be invoked on the instance of the Java class that is the resource associated with delivery 2 of invoice 1.