Friday, April 4, 2008

Generics Madness

So I just came back from the ACM-SE conference in Auburn at which I gave a talk on generics (slides here). I also gave this talk at Rosetta Stone shortly beforehand. I’ve been considering an interesting extension to the example from the paper; Trent Bowman (of Rosetta Stone) had suggested to me that it might be interesting to enable InvokerProxy types to enforce a restriction on the types of Commands they may invoke.


Suppose we want to decorate our Invoker with someone that only accepts a special type of command - say, an AuthenticatedCommand:

public class AuthenticatedCommand<T, R extends Renderer>
implements RendererCommand<T, R> {
private final AuthenticationToken token;
private final RendererCommand<T,R> command;

protected AuthenticatedCommand(RendererCommand<T, R> command, 
AuthenticationToken token) {
this.command = command;
this.token = token;
}

public static <T, R extends Renderer> AuthenticatedCommand<T, R> create(
RendererCommand<T,R> command, AuthenticationToken token) {
return new AuthenticatedCommand<T, R>(command, token);
}

public AuthenticationToken getToken() {
return token;
}

public RendererCommand<T, R> getCommand() {
return command;
}

public T execute(R renderer) {
return null; // .. no implementation - not used
}
}


Recall the implementation of RendererService:
public interface RendererService<R extends Renderer> {
<T> T invoke( RendererCommand<T,R> command );
}


Next, we can overload the invoke() method in AuthenticatedRendererService:
public class AuthenticatedRendererService<R extends Renderer> implements
RendererService<R> {

public AuthenticatedRendererService( RendererService<R> decorated ) {
this.decoratedService = decorated;
}

private RendererService<R> decoratedService;

public <T> T invoke(AuthenticatedRendererCommand<T, R> command) {
System.out.println("Authenticating command");
AuthenticationToken token = command.getToken();
if (verifyToken(token)) {
return invoke( command.getCommand() );
} else {
throw new RuntimeException();
}
}

public <T> T invoke(RendererCommand<T, R> command) {
return decoratedService.invoke(command);
}

private boolean verifyToken(AuthenticationToken token) {
return true;
}

}


And a sample usage:
AuthenticatedRendererService<Rasterizer> authenticatedRasterizer = 
getAuthenticatedRasterizer();
AuthenticatedRendererCommand<Dimension, Rasterizer> authenticatedGetSize = 
new AuthenticatedRendererCommand<Dimension, Rasterizer>(new GetSize(), 
getAuthenticationToken());
Dimension result = authenticatedRasterizer.invoke( authenticatedGetSize );



Output: “Authenticating Command”

Wonderful! Now, let’s add yet another decorator by implementing a LoggingRendererService:

public class LoggingRendererService<R extends Renderer> 
implements RendererService<R> {
private RendererService<R> decorated;
public <T> T invoke(RendererCommand<T,R> command) {
System.out.println("Logging command");
decorated.invoke(command);
}
}


Let’s expand our example by decorating our authenticatedRasterizer with a LoggingRendererService:

AuthenticatedRendererService<Rasterizer> authenticatedRasterizer =
getAuthenticatedRasterizer();
AuthenticatedRendererCommand<Dimension, Rasterizer> authenticatedGetSize = 
new AuthenticatedRendererCommand<Dimension, Rasterizer>(new GetSize(), 
getAuthenticationToken());
RendererService<Rasterizer> loggingAuthenticatedRasterizer = new 
LoggingRendererService<Rasterizer>( authenticatedRasterizer );
secondDecorator.invoke( authenticatedGetSize );


Output: “Logging Command”

Wait.. What happened to our AuthenticatingCommand’s overloaded invoke() method? Why was the overloaded invoke() method not called on that object? The answer is that method invocations in Java are bound at compile time, not at runtime. Therefore, the non-overloaded version of AuthenticatedRendererService#invoke() will always be called when the calling context specifies a RendererCommand instead of an AuthenticatedRendererCommand. Therefore, we cannot achieve arbitrary decoration/proxying through the use of overloaded methods (At least, in languages that do not feature multiple dispatch such as Java)

Alternatively, we could try to specify the type of the Command to be run directly on the RendererService. In order for the InvokerProxy to require a specific type of Command, we must change the Invoker interface:

public interface RendererService<R extends Renderer, 
C extends RendererCommand<?, R>> {
<T> T invoke( C command );
}


Notice how we’ve kept the method-level type parameter T as the return type. However, we’ve lost the opportunity to link T to the return type of our RendererCommand. Watch out, because this is going to come back to bite us in the ass later. Now let us look at an implementation of an AuthenticatedRendererService:

public class AuthenticatedRendererService<R extends Renderer> implements
RendererService<R, AuthenticatedCommand<?, R>> {

private RendererService<R, RendererCommand<?, R>> decoratedService;

public <T> T invoke(AuthenticatedCommand<?, R> command) {
AuthenticationToken token = command.getToken();
if (verifyToken(token)) {
return decoratedService.invoke(command.getCommand());
} else {
throw new RuntimeException();
}
}

private boolean verifyToken(AuthenticationToken token) {
return true;
}
}


An example usage of this class:

AuthenticatedRendererService<Rasterizer> rasterizer = 
getAuthenticatedRasterizerService();

AuthenticatedCommand<Dimension, Rasterizer> authenticatedGetSize = 
AuthenticatedCommand.create(new GetSize(), null);

Point2D screenSize = rasterizer.invoke(authenticatedGetSize);


Ouch! The original error in the paper (assigning the result of Rasterizer#getSize() to a Point2D instead of a Dimension) has returned. Let’s examine why this occurred.

The fault lies in the method type parameter T in the invoke() method of RendererService. As I mentioned, we can no longer establish a relationship between this type parameter and the Command being invoked because we’ve added the Command’s type as an interface-level type parameter to RendererService. Furthermore, we specified the wildcard as its return type because we don’t want to make a RendererService specific to one return type. Since the compiler can’t bind our method-level parameter T to a type on the Command, it performs a little trick called type argument inference to essentially use the type of the assignment of the return value (in this case Point2D) to bind the type T. This means that we can assign the return value of the invoke() method to ANY local variable, regardless of type. Busted.

What we really want here is the ability to defer a class-level type binding. Then, we want to let the compiler establish a link between the deferred type and a method-level type parameter such that type safety is guaranteed for that specific method invocation. What follows is an extremely informal description of how such a system might work. It is likely broken in some ways. Please let me know if you can think of instances in which this would not work!

Suppose we introduce a new token (*) as a modifier on a class-level type parameter. This modifier tells the compiler not to attempt to bind this value immediately, but to defer binding until, in this case, a method-level type parameter can provide the necessary type information for it. We can now change our RendererService definition:

public interface RendererService<R extends Renderer, V*, C extends RendererCommand<V, R>> {
<T binds V> T invoke( C command );
}


And, our AuthenticatedRendererService definition:

public class AuthenticatedRendererService<R extends Renderer, V*> implements
RendererService<R, AuthenticatedCommand<V, R>> {

private RendererService<R, RendererCommand<V, R>> decoratedService;

// some code omitted..
public <T binds V> T invoke(AuthenticatedCommand<T, R> command) {
AuthenticationToken token = command.getToken();
if (verifyToken(token)) {
return decoratedService.invoke(command.getCommand());
} else {
throw new RuntimeException();
}
}
}


(Please note that we bound RendererService’s deferred V type parameter with another deferred type parameter).

Now, our example should yield an error, since we’ve reestablished the link between the method level type parameter and the command:
// Will result in a compile time error.
Point2D screenSize = rasterizer.invoke(authenticatedGetSize); 


However, there are a lot of cases in which this can get fishy. In the new version of AuthenticatedRendererService, you can see we’re holding on to an actual instance that’s bound to V (our decoratedService). This can get us into trouble if we start using that instance without binding V!

public class AuthenticatedRendererService< R extends Renderer, V*> implements 
RendererService<R, V, AuthenticatedCommand<V,R>> {
private RendererService<R, RendererCommand<V, R>> decoratedService;

public RendererService<R, RendererCommand<V, R>> getDecoratedService() {
return decoratedService;
}
}


Uh oh, now we’ve exposed this deferred type parameter to the outside world!. We could ensure that this type doesn’t escape by adding a requirement that all nonstatic methods which refer to a deferred type parameter must bind something to that type parameter. Or, we could treat it in a manner similar to the wildcard (?) operator until it is bound.

I’m going to leave this as an unfinished thought, but I figured I’d throw it out there to see what people might think Send me comments!

No comments:

Post a Comment